本文最后更新于:2022年7月4日 上午
栈是一种先进后出、后进先出 的数据结构,栈和队列应该是最简单的两种数据结构了,其原理与实现非常简单。单调栈中的元素是严格单调递增或者递减的 ,也就是说:从栈底到栈顶,元素的值逐渐增大或者减小 。本文介绍单调栈的优势和应用。
简介
单调栈,就是一个栈,不过栈内元素保证单调性。即,栈内元素要么从小到大,要么从大到小。而单调栈维护的就是一个数前/后第一个大于/小于他的数。
栈运作方式
单调栈本质上也是栈,只是有一套特定的运算规则,我们以单调递增栈 为例讲解
单调栈维护栈内元素非减,即新入栈的元素不会小于当前的栈顶
当待入栈元素小于当前栈顶时,这个元素也是要入栈的,这是最优先的事项,那么为了维护栈的单调性,栈顶元素需要出栈,直到栈顶不大于当前元素或栈为空
单调栈示意图
在算法应用中主要用于查找数组中最近的比当前值大 / 小的数据下标
应用示例
例 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 来代替。
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)
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
参考资料