Fulongのblog

单调队列和单调栈

2021/06/21 Algorithms 共 4317 字，约 13 分钟

单调栈和单调队列

单调栈用于求下一个比它大或者比它小的。o(n)。 或者是左边最小的。

单调队列在此基础上可以筛选头部不要的元素。

当访问到第 i 个元素时，单调栈维护的区间为 [0, i) ，而单调队列维护的区间为 (last_pop, i)。因此单调队列可以做一些比如j-i<N的限制维护单调队列。

单调栈总结：如果压栈之后仍然可以保持单调性，那么直接压。否则先弹出栈的元素，直到压入之后可以保持单调性。 这个算法的原理用一句话总结就是，被弹出的元素都是大于当前元素的，并且由于栈是单调增的，因此在其之后小于其本身的最近的就是当前元素了

单调栈可利用的点

维护一个栈， 最终目的是把当前元素append进去，因此可能对pop一些元素，可利用的就是pop的这些元素，和最后插入元素这两个时机。

如果是递减栈，则插入过程中被Pop掉的都是小于当前i的值， 因此对于pop元素，求的是的右边第一个大，对i也知道左边第一个小。

  • 因此求右边第一个大的，可以递减栈，从左往右遍历，弹出时操作。 也可以顺便求左边第一个大的，在push时操作。

  • 求右边第一个小的，可以递增栈，从左往右遍历，弹出时操作。

  • 求左边第一个大的，可以递减栈，从右往左遍历，弹出时操作。

  • 求左边第一个小的，可以递增栈，从右往左遍历，弹出时操作。

模板：

求左右两边第一个小的：84. 柱状图中最大的矩形 单调栈存的是左右两边第一个小的索引, 这样左右边界就是大于等于当前高度的位置。 就可以得到当前值为高度的最大横向长度，从而得到最大面积。

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        if not heights:
            return 0
        n = len(heights)
        l = [-1 for _ in range(n)]
        r = [n for _ in range(n)]
        stack = []
        for i, h in enumerate(heights):
            while stack and heights[stack[-1]] >= h:
                r[stack[-1]] = i
                stack.pop()
            l[i] = stack[-1] if stack else -1
            stack.append(i)
        ans = max(h * (r[i] - l[i] - 1) for i, h in enumerate(heights))
        return ans

注意以上求法是非严格小的。

严格小的：对于stack[-1]，它左右两边就是严格小的。，参考：

场景：

  • 求左边/右边 第一个比a[i]大/小的值。
  • 求左边/右边 持续的a[i]<a[j]或者a[i]>a[j]的值。
  • 利用单调栈做一些合并，比如901. 股票价格跨度 求出小于或等于今天价格的最大连续日数等价于求出最近的一个大于今日价格的日子。使用单调栈，元素weight进行合并。再比如题目: 1130. 叶值的最小代价生成树 ， 1504. 统计全 1 子矩形
  • 求不重复的字典序字符串 一个经典问题，求长为 k的字典序最小子序列， counter这些都是额外的限制。
  • 求A[i]<A[j]的最大j-i, 最大宽度坡
  • 求和大于0的最长子数组, 参考 先一次算好递减的stack，然后从后往前遍历不停pop，不新增栈。其实就是先求前序和，然后pre上求最大宽度坡。
  • 左边递减小于当前值的列表，接雨水等求面积时使用。
  • 左右两边第一个小于它的位置，也可以得到不左右两边连续大于等于当前值的最后一个位置。求最大面积时使用。84. 柱状图中最大的矩形 计算左右两边第一个小的位置i,j, 然后用i,j就可以求出矩形面积了，可以一次遍历求出。

相关题目

  • 力扣加加
  • 1944. 队列中可以看到的人数 统计右边连续A[i]<A[j]的数量。
  • 42. 接雨水 ，其实是递减栈，从左到右，求当前值为右边界情况下小于右边界的每个左边界的累计面积。 正好是pop弹出时做的操作。高度为左右两边最低高度 - pop位置的高度，这个横着的矩形。
  • 739. 每日温度 求在每一天需要等几天才会有更高的温度。实际就是求下一个更大值的位置。
  • 1081. 不同字符的最小子序列 用递增栈维护子序列，遍历到i时， 当在栈里直接continue, 当栈顶的字符后面不会再出现时，不能pop。
  • 求A[i]<A[j]的最大j-i, 最大宽度坡 维护有序数组或者按照大小对1,2,3,4…排序。
  • 85. 最大矩形 变成柱状图中最大矩形即可。
  • 402. 移掉 K 位数字 求移除这个数中的 k 位数字，使得剩下的数字最小。直接维护一个递增栈，有能删的就删。
  • 901. 股票价格跨度 求出小于或等于今天价格的最大连续日数等价于求出最近的一个大于今日价格的日子。使用单调栈，元素weight进行合并。
  • 907. 子数组的最小值之和 求以arr[i]作为最小值的subarray数量= left_count*right_count. 注意这里取左开右闭。实际就是先求以arr[i]左右两边最小值的位置。
  • 1504. 统计全 1 子矩形 单调栈合并。先求直方图，再从上往下遍历，求(i,j)为右下角顶点的个数，单调栈记录了(left(i,j), height), height是合并后的count. 是当前为最大宽度时，上面宽度递减的子矩阵总数。
  • 1130. 叶值的最小代价生成树 每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积。求返回每个非叶节点的值的最小可能总和。类似hufflman树，小的在下面，单调栈，如[6,2,4]，插入4时，合并2和4, 变成[6,4],ans+= 2*4

求左边右边, 最小的大于等于arr[i]的位置，一种方式是sortedList, 一种方式是sorted(range(N), lambda x:arr[x])

最大宽度 最大上升坡

求最大坡度, 坡度定义: i < j 且 A[i] <= A[j]。这样的坡的宽度为 j - i。找每个元素比它大的最后一个位置 可以按https://leetcode.cn/submissions/detail/208988818/ 中，按val对range(n)排序，o(nlogn)，此时对排序位置i的元素最大坡度就是右边最大j。此时右边元素都不小于当前元素。

class Solution:
    def maxWidthRamp(self, nums: List[int]) -> int:
        ans = 0
        m = float('inf')
        for i in sorted(range(len(nums)), key=lambda x: nums[x]):
            ans = max(ans, i - m)
            m = min(m, i)
        return ans

也可以单调栈o(n)求，先求正序递减栈，然后倒序枚举，如果比栈顶大，则栈顶元素后续就无用可pop了


class Solution:
    def maxWidthRamp(self, nums: List[int]) -> int:
        ans = 0
        stack = []
        for i, v in enumerate(nums):
            if not stack or v < nums[stack[-1]]:
                stack.append(i)
        # print(stack)
        for i in range(len(nums) - 1, -1, -1):
            while stack and nums[i] >= nums[stack[-1]]:
                ans = max(ans, i - stack.pop())
        return ans

类似题目：

单调队列

求一定范围内最大的某个值，当i<j时，如果dp(i)<dp(j), 那dp(i)就没有存在的必要了，因此可以队列递减。

可以o(logn)的复杂度用sortedlist实现，sortedlist就是可删除的堆。

维护一个单调递增的栈：参考

单调队列可动态维护滑动窗口的最大值最小值，递减队列就是维护最大值，可限制窗口长度、绝对值差之类的

队列解决滑动窗口

  • 239. 滑动窗口最大值 当i<j and nums[i]<nums[j] 当滑动窗口向右移动时，只要 i 还在窗口中，那么 j 一定也还在窗口中，这是 ii 在 jj 的左侧所保证的。因此，由于 nums[j] 的存在，nums[i] 一定不会是滑动窗口中的最大值了，我们可以将 nums[i] 永久地移除。所以可以用个递减单调队列。
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        ans = []
        import collections
        q = collections.deque()
        for i in range(k-1):
            while q and q[-1][0] <= nums[i]:
                q.pop()
            q.append((nums[i], i))
        for i in range(k-1, len(nums)):
            v = nums[i]
            while q and q[-1][0] <= v:
                q.pop()
            q.append((v, i))
            while q and q[0][1] <= i - k:
                q.popleft()
            ans.append(q[0][0])
        return ans
  • 剑指 Offer 59 - II. 队列的最大值 请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
  • 1425. 带限制的子序列和 给你一个整数数组 nums 和一个整数 k ，请你返回 非空 子序列元素和的最大值，子序列需要满足：子序列中每两个 相邻 的整数 nums[i] 和 nums[j] ，它们在原数组中的下标 i 和 j 满足 i < j 且 j - i <= k 。 解答：该题可以通过队列递减，同时用数组维护index i的值，f(i)为用了i的值的最大值，f(i) = max(f(j)+nums[i]), j是符合条件的.
  • 1499. 满足不等式的最大值 请你找出 yi + yj + |xi - xj| 的 最大值，其中 |xi - xj| <= k 且 1 <= i < j <= points.length。
  • 1438. 绝对差不超过限制的最长连续子数组 给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。 维护max, min的队列，同时双指针，不断移动左指针。

求一定范围内差值最大，可以队列递增，这样每次与队列头比较下就可以了，同时i<j,dp(i)>dp(j), dp(i)也没机会用到，所以是队列递增。

Search

    Table of Contents

    Popular Posts