单调栈

本文最后更新于：2022年5月21日 凌晨

栈是一种先进后出、后进先出的数据结构，栈和队列应该是最简单的两种数据结构了，其原理与实现非常简单。单调栈中的元素是严格单调递增或者递减的，也就是说：从栈底到栈顶，元素的值逐渐增大或者减小。本文介绍单调栈的优势和应用。

简介

单调栈，就是一个栈，不过栈内元素保证单调性。即，栈内元素要么从小到大，要么从大到小。而单调栈维护的就是一个数前/后第一个大于/小于他的数。

  • 因此单调栈分为两种“

    • 单调递增栈：

      ①在一个队列中针对每一个元素从它右边寻找第一个比它小的元素

      ②在一个队列中针对每一个元素从它左边寻找第一个比它小的元素

    • 单调递减栈：

      ①在一个队列中针对每一个元素从它右边寻找第一个比它大的元素

      ②在一个队列中针对每一个元素从它左边寻找第一个比它大的元素

  • 虽然单调栈的性质很简单，但是其用处很大，可以用于求解元素的左右大小边界问题。

栈运作方式

  • 单调栈本质上也是栈，只是有一套特定的运算规则，我们以单调递增栈为例讲解
  • 单调栈维护栈内元素非减，即新入栈的元素不会小于当前的栈顶
  • 当待入栈元素小于当前栈顶时，这个元素也是要入栈的，这是最优先的事项，那么为了维护栈的单调性，栈顶元素需要出栈，直到栈顶不大于当前元素或栈为空

  • 在算法应用中主要用于查找数组中最近的比当前值大 / 小的数据下标

应用示例

例 1

P5788 【模板】单调栈

  • 题目描述

给出项数为 $n$ 的整数数列 $a_{1…n}$。

定义函数$ f(i)$ 代表数列中第 $i$ 个元素之后第一个大于$ a_i$ 的元素的下标，即$ f(i)=\min {i<j \leq n, a{j}>a_{i}}{j} $。若不存在，则$ f(i)=0$。

试求出 $f(1…n)$。

  • 输入格式

第一行一个正整数 $n$。

第二行 $n$个正整数 $a_{1…n}$。

  • 输出格式

一行 $n$个整数 $f(1…n)$ 的值。

同 剑指 Offer II 038 每日温度

请根据每日 气温 列表 temperatures ，重新生成一个列表，要求其对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

  • 可以用单调递减栈，当遇到较大值出栈时记录偏差下标，时间复杂度 $O(n)$

  • 参考代码

1
2
3
4
5
6
7
8
9
10
class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        res_list = [0] * len(temperatures)
        data_stack = list()
        for index, item in enumerate(temperatures):
            while data_stack and data_stack[-1][0] < item:
                value, mark_index = data_stack.pop()
                res_list[mark_index] = index - mark_index
            data_stack.append([item, index])
        return res_list
  • 事实上这道题我在不知道单调栈时第一反应是维护短暂的优先队列
  • 正常用堆维护的优先队列实现的话，理论上时间复杂度为 $ O(nlog(n))$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        from sortedcontainers import SortedDict
        from sortedcontainers import SortedList
        res_list = [0 for _ in temperatures]
        target_dict = SortedDict()
        for index, item in enumerate(temperatures):
            while len(target_dict) > 0 and list(target_dict.keys())[0] < item:
                tar_key = list(target_dict.keys())[0]
                index_list = target_dict[tar_key]
                for mark_index in index_list:
                    res_list[mark_index] = index - mark_index
                target_dict.pop(tar_key)
            if item not in target_dict:
                target_dict[item] = SortedList()
            target_dict[item].add(index)
        return res_list
  • 实现上用的是排序队列，我们需要的仅是维护最大值就可以了，因此浪费了算力，运行时间是单调栈的十倍

例 2

力扣（LeetCode） 496. 下一个更大元素 I

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

  • 为 nums2 使用递减单调栈找到第一个比自己大的元素值并建立字典，nums1 中元素在其中查找填值即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        num1_len = len(nums1)
        num2_len = len(nums2)
        res_dict = {nums2[index]: -1 for index in range(num2_len)}
        res_list = [-1] * num1_len
        data_stack = list()
        for num in nums2:
            while data_stack and num > data_stack[-1]:
                value = data_stack.pop()
                res_dict[value] = num
            data_stack.append(num)
        for index, value in enumerate(nums1):
            if value in res_dict:
                res_list[index] = res_dict[value]
        return res_list

例 3

力扣（LeetCode）84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

1
2
3
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
  • 需要知道的是每个柱子左右两边小于自己的柱子的下标，然后可以计算出每个柱子为高度的矩形最大的宽度
  • 之后算出每个柱子的最大面积，再取大家的最大值即可
  • 时间复杂度为两个方向寻找第一个比自己小的元素下标计算，O(n) * 2
  • 求取最大值并取最大值时间复杂度 O(n)
  • 总的时间复杂度 O(n)
  • 参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    @staticmethod
    def first_smaller(heights: list, direction):
        assert direction in ['left', 'right']

        def r_search(heights, res_list):
            stack = list()
            for index, height in enumerate(heights):
                while stack and height < stack[-1][0]:
                    _, mark_index = stack.pop()
                    res_list[mark_index] = index
                stack.append([height, index])
            return res_list

        if direction == 'right':
            res_list = [len(heights)] * len(heights)
            right_points = r_search(heights, res_list)
            return right_points

        elif direction == 'left':
            res_list = [len(heights)] * len(heights)
            left_points = r_search(heights[::-1], res_list)
            left_points = [len(heights) - value for value in left_points]
            return left_points[::-1]

    def largestRectangleArea(self, heights: List[int]) -> int:
        left_points = self.first_smaller(heights, 'left')
        right_points = self.first_smaller(heights, 'right')
        area_list = [(right_points[index] - left_points[index]) * heights[index] for index in range(len(heights))]
        return max(area_list)

  • 上述代码时间复杂度已经优化到极限了，但是事实上逻辑还可以继续简化

  • 可以在柱子左右端加入 [0] 元素作为哨兵来完善边界条件

  • 之后其实可以在仅做一边的单调栈：

    • 检测左到右的第一个小于当前元素的下标，应用标准单调栈
    • 在出栈后，当前栈顶元素可以作为出栈柱子宽度的左边界
    • 每次出栈后计算出栈元素的矩形面积，维护最大值返回即可

  • 参考代码

1
2
3
4
5
6
7
8
9
10
def largestRectangleArea2(self, heights: List[int]) -> int:
    data_stack = list()
    heights = [0] + heights + [0]
    res = 0
    for index in range(len(heights)):
        while data_stack and heights[data_stack[-1]] > heights[index]:
            out_index = data_stack.pop()
            res = max(res, heights[out_index] * (index - data_stack[-1] - 1))
        data_stack.append(index)
    return res
  • 时间复杂度是相同的，常数项更小了

例 4

力扣（LeetCode）42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

1
2
3
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
  • 建立单调递减栈，检查比当前值大的下一个元素
  • 每个水坑的水需要由下到上一行一行计算累加
  • 需要维护池底高度、当前水位（min(left, right))和水槽宽度(right - left + 1)
  • 参考代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def trap(self, height: List[int]) -> int:
        water = 0
        stack = list()
        for index in range(len(height)):
            below = -1
            mark_index = None
            while stack and height[index] >= height[stack[-1]]:
                mark_index = stack.pop()
                if below < 0:
                    below = height[mark_index]
                else:
                    water += (min(height[index], height[mark_index]) - below) * (index - mark_index - 1)
                    below = height[mark_index]
            if mark_index is not None and stack:
                water += (height[index] - height[mark_index]) * (index - stack[-1] - 1)
            stack.append(index)
        return water

参考资料

Algorithm
Algorithm

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！