stack

写此系列博客的榜样来自：leetcode cookbook

单调栈

单调栈基础

作者：Shawxing精讲算法
链接：https://leetcode.cn/discuss/post/L5ZpxA/

在 O(n) 的时间复杂度内求出数组中各个元素右侧第一个更大的元素及其下标，然后一并得到其他信息。

原理

最终结果

代码

class Solution:
    def monotonicStack(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [0] * n
        st = []

        for i, v in enumerate(nums):
            while st and v > nums[st[-1]]:
                prevI = st.pop()
                ans[prevI] = i
                # 还可以针对 prevI, i, nums[prevI], nums[i] 做些其他的处理 
            st.append(i)
        
        return ans

相关题目

T239 滑动窗口最大值

这是一个降本增笑的故事（参考灵茶山艾府的解析）：

如果新员工比老员工强（或者一样强），把老员工裁掉。（元素进入窗口）
如果老员工 35 岁了，也裁掉。（元素离开窗口）
裁员后，资历最老（最左边）的人就是最强的员工了。

def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        ans=[0]*(len(nums)-k+1)
        q=deque() #双端队列

        for i,x in enumerate(nums):
            # 1.右边入
            while q and nums[q[-1]]<=x:
                q.pop()
            q.append(i)

            # 2.左边出
            left=i-k+1
            if q[0]<left:
                q.popleft()

            # 3.在窗口左端点处记录答案
            if left>=0:
                ans[left]=nums[q[0]]
        return ans