单调栈

本文最后更新于: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

参考资料


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