基础算法6 - 单调栈
站长
· 阅读数 4
概念 & 应用
通常是一维数组，要寻找任一个元素的右边/左边第一个比自己大/小的元素的位置，此时我们就要想到可以用单调栈了。
单调栈的本质是空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素（大/小）的元素，优点是只需要遍历一次。
单调栈何时用
为任意一个元素找左边和右边第一个比自己大/小的位置，用单调栈
用递增单调栈 or 递减单调栈
- 找最大值：递减栈会剔除波谷，留下波峰；
- 找最小值：递增栈剔除波峰，留下波谷
模版
三步走：
- 维持递增/减栈
- 放入最后结果array
- 当前元素/index入栈
vector<int> nextGreaterElement(vector<int>& nums) {
vector<int> res(nums.size()); // 存放答案的数组
stack<int> s;
// 倒着往栈里放
for (int i = nums.size() - 1; i >= 0; i--) {
// 判定个子高矮
while (!s.empty() && s.top() <= nums[i]) {
// 矮个起开，反正也被挡着了。。。
s.pop();
}
// nums[i] 身后的 next great number
res[i] = s.empty() ? -1 : s.top();
s.push(nums[i]);
}
return res;
}
LC739 每日温度（Medium）
Solution：单调栈
- 照抄单调栈模版
- 因为要计算距离，所以stack里存储index
Code：
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
ans = [0] * len(temperatures)
stack = []
for i in range(len(temperatures) - 1, -1, -1):
while stack and temperatures[i] >= temperatures[stack[-1]]:
stack.pop()
if stack:
ans[i] = stack[-1] - i
else:
ans[i] = 0
stack.append(i)
return ans
下一个更大元素
LC496 下一个更大元素 I（Easy）
Solution：
dictionary记录nums2中每个元素对应的next greater element。统计完之后，找出nums1中每个元素对应的entry放入ans即可
Code：
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
stack = []
ans = []
dic = {}
for i in range(len(nums2) - 1, -1, -1):
while stack and stack[-1] <= nums2[i]:
stack.pop()
num = stack[-1] if stack else -1
dic[nums2[i]] = num
stack.append(nums2[i])
for x in nums1:
ans.append(dic[x])
return ans
LC503 下一个更大元素 II（Medium）
Solution：
解决「环形数组」常用套路：将数组长度翻倍 + % 运算符求模（余数）
- 可以不用真的去构造一个新数组，而是利用循环数组的技巧来模拟数组长度翻倍的效果
Code：
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
stack = []
res = [-1] * len(nums)
# 假装把nums长度翻倍
for i in range(2 * len(nums) - 1, -1, -1):
while stack and stack[-1] <= nums[i % len(nums)]:
stack.pop()
res[i % len(nums)] = stack[-1] if stack else -1 # overwrite
stack.append(nums[i % len(nums)])
return res
LC42 接雨水（Hard）
Solution 1：单调栈 ❤️
- “下降期”是无法储水的，要遇到上升的元素时，才需要去检视
- 需要3个元素来储水：左墙壁+右墙壁+湖底
- 需满足
min{左墙壁, 右墙壁} > 湖底（形成“凹槽”） 储水量 = (最小高度差min{左墙壁, 右墙壁} - 湖底) * (宽度right_idx - left_idx)
- 需满足
Code 1：
class Solution:
def trap(self, height: List[int]) -> int:
stack = [] # 单调递减栈,存index以便计算宽度
res = 0
for i in range(len(height)):
while stack and height[i] > height[stack[-1]]:
bottom = stack.pop() # 湖底
if not stack: # 没有左墙壁
break
res += max(min(height[i], height[stack[-1]]) - height[bottom], 0) * (i - stack[-1] - 1) # 高度差 * 宽度
stack.append(i)
return res
Solution 2：DP
- 两次dp，分别计算出对于每一column[i]，其左侧和右侧的max_height分别为多少
- 对于每一列，其是否能存于水取决于
min{i左侧max_height，i右侧max_height}是否严格 > column[i]- 如果成立，column[i]的储水量 =
min{i左侧max_height，i右侧max_height} - column[i]
- 如果成立，column[i]的储水量 =
Code 2：
class Solution:
def trap(self, height: List[int]) -> int:
maxL, maxR = [0] * len(height), [0] * len(height)
maxL[0], maxR[-1] = -1, -1
# 两次DP, find the max height on the left and right
for i in range(1, len(height)):
maxL[i] = max(maxL[i - 1], height[i - 1])
for i in range(len(height) - 2, -1, -1):
maxR[i] = max(maxR[i + 1], height[i + 1])
res = 0
# find the total water
for i in range(len(height)):
res += max(0, min(maxL[i], maxR[i]) - height[i])
return res
84. 柱状图中最大的矩形（Hard）
Solution 1：Divide & Conquer
- 每次根据当前最矮的column做分割
- 最终
max_area = max{在最矮柱子左边的最大面积矩形（子问题）, 在最矮柱子右边的最大面积矩形（子问题）, (end - start) * min_height}- 因为是以最矮的column分割的，所以想要连通左右两半，只能是以min_height为高度，(end - start)为宽度
Code 1：
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
def find_max_area(l, r) -> int:
if l > r:
return
if l == r:
return heights[l]
else:
min_idx = l
for i in range(l, r + 1):
if heights[i] < heights[min_idx]:
min_idx = i
return max(heights[min_idx] * (r - l + 1), find_max_area(l, min_idx - 1), find_max_area(min_idx + 1, r))
return find_max_area(0, len(heights) - 1)
Solution 2： ❤️
- “上升期”时不需要计算面积的，因为向前一格总能得到比当前
max_area更大的面积 - 遇到“下降期”时，可以着手计算当前stack里的矩形们可以产生的
max_area（暴力枚举）- 随着高度的下降，更多的竖条可以加入到大长方形的面积中
Code 2：
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
heights = heights + [0] # 在尾部加一个dummy的0，就不需要单独再while-loop检视最后一轮"上升期"一次了
stack = []
res = 0
for i in range(len(heights)):
while stack and heights[i] < heights[stack[-1]]: # 遇到"下降期"，值得去计算
# 不能直接用pop出来的index去计算width，因为这样可能导致之前相同高度的矩形（pop后stack[-1]之前的）被漏掉
h = heights[stack.pop()]
w = i if not stack else i - stack[-1] - 1
res = max(res, h * w)
stack.append(i)
return res
85. 最大矩形（Hard）
Solu：前缀和 + 单调栈
见上图，本题可以转化为和84. 柱状图中最大的矩形一样
- 单调栈：枚举每一行作为底部水平基线（x轴），求出以这条基线为底的
max(S矩形) - 前缀和：
preSum[i][j] = #'1' above matrix[i][j]（包括matrix[i][j]）-
preSum[i][j] = preSum[i-1][j] + 1 if matrix[i][j] == '1' else 0
-
Code：
一维滚动数组优化
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
# 参考LC84
def largestRectangleArea(heights: List[int]) -> int:
heights = heights + [0] # 在尾部加一个dummy的0，就不需要单独再while-loop检视最后一轮"上升期"一次了
stack = []
res = 0
for i in range(len(heights)):
while stack and heights[i] < heights[stack[-1]]: # 遇到"下降期"，值得去计算
# 不能直接用pop出来的index去计算width，因为这样可能导致之前相同高度的矩形（pop后stack[-1]之前的）被漏掉
h = heights[stack.pop()]
w = i if not stack else i - stack[-1] - 1
res = max(res, h * w)
stack.append(i)
return res
sumRegion = [0] * len(matrix[0]) # 一维滚动数组优化
max_area = 0
for i in range(len(matrix)): # 以每一行为底部基线（x轴）
for j in range(len(matrix[0])):
sumRegion[j] = sumRegion[j] + 1 if matrix[i][j] == '1' else 0
max_area = max(max_area, largestRectangleArea(sumRegion))
return max_area
最大/小的剩余序列
- 删除或保留若干个字符，使得「剩下的数字最小/大 或者 字典序最小/大」=> 贪心 + 单调栈！！！
- 解决问题的前提是要有一定“数学前提”
- 再基于这个数学前提，我们贪心地删除栈中相邻的字符
316. 去除重复字母（Medium）
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
示例 1：
输入：s = "bcabc" 输出："abc" 示例 2：
输入：s = "cbacdcbc" 输出："acdb"
思路：
- 尽量保持递增的stack（字典序需要用单调栈）
- if
遇到下一个更小（会破坏当前的单调性）&& 前面的char未来还会再出现-> then 把前面的char给pop出去，生成最小序列
代码：
class Solution:
def removeDuplicateLetters(self, s: str) -> str:
stack = []
dic = collections.Counter(s)
for c in s:
if c not in stack: # 去重
while stack and c <= stack[-1] and dic[stack[-1]] > 0:
stack.pop()
stack.append(c)
dic[c] -= 1
return ''.join(stack)
402. 移掉 K 位数字（Medium）
给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
示例 1 ：
输入：num = "1432219", k = 3 输出："1219" 解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。
思路：
- 保持一个递增的stack，每次出现更小的digit时，就把前面更大的digits给顶替掉
- 可替换的次数保证 ≤ k
- 注意：如果原始的num就已经保持了单调递增，那么必须要强行删除k个！
代码：
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
stack = []
for c in num:
while k and stack and stack[-1] > c:
stack.pop()
k -= 1
stack.append(c)
if k:
stack = stack[:-k]
return ''.join(stack).lstrip('0') or '0'
1673. 找出最具竞争力的子序列（Medium）
Solu：Greedy + 单调栈
stack维护一个最小的单调递增子序列- “贪心”思想：肯定希望以更小的数字作为子序列的开头，这样更有“竞争力”
to_delete= #需要删除的数字 =len(nums)-k- 一旦
to_delete == 0，就说明不能再删（pop）了，直接把nums[i]往stack里放 - 如果遍历完之后
to_delet > 0，说明stack里维护着的子序列太长了，要裁掉最后的几位，保证len(stack) == k
- 一旦
Code：
class Solution:
def mostCompetitive(self, nums: List[int], k: int) -> List[int]:
stack = [] # 保留最小的单调递增子序列
to_delete = len(nums) - k # number of elements to delete
for i in range(len(nums)):
while stack and stack[-1] > nums[i] and to_delete > 0:
stack.pop()
to_delete -= 1
stack.append(nums[i])
while to_delete > 0:
stack.pop()
to_delete -= 1
return stack
i 左/右侧第一个 < nums[i]的索引
1856. 子数组最小乘积的最大值（Medium）
Solu：
- 枚举数组中每个值
num，并且以num作为子数组中的最小值，再乘以这个子数组的和（前缀和），通过“打擂台”的方式得到最终答案。 - 于是问题变成：给定
num及其索引idx，如何找到以num为最小值的子数组边界- 转化成：对于数组中的每一个元素，分别找到其左边、右边第一个比它小的元素的位置
Code：
class Solution:
def maxSumMinProduct(self, nums: List[int]) -> int:
# 左右添加两个哨兵，方便单调栈内的判断
nums = [0] + nums + [0]
# 前缀和
presum = [0]
for n in nums:
presum.append(presum[-1] + n)
def right_first_smaller(): # nums[i]右侧（倒数）第一个比nums[i]小的数
res = [None] * len(nums)
stack = []
for i in range(len(nums)):
while stack and nums[i] < nums[stack[-1]]:
res[stack.pop()] = i
stack.append(i)
return res
def left_first_smaller(): # nums[i]左侧（正数）第一个比nums[i]小的数
res = [None] * len(nums)
stack = []
for i in range(len(nums) - 1, -1, -1):
while stack and nums[i] < nums[stack[-1]]:
res[stack.pop()] = i
stack.append(i)
return res
right_first_smaller = right_first_smaller()
left_first_smaller = left_first_smaller()
res = 0
for i in range(1, len(nums) - 1):
left = left_first_smaller[i]
right = right_first_smaller[i]
res = max(res, nums[i] * (presum[right] - presum[left + 1]))
return res % (10 ** 9 + 7)
统计≤/≥nums[i]的连续个数
单调递减/增栈存储tuple (nums[i], ≤/≥nums[i]的连续个数)
901. 股票价格跨度（Medium）
Solu：
- 栈中存放递减序列对
(price, w)
Code：
class StockSpanner:
def __init__(self):
self.stack = [] # 单调递增栈
def next(self, price: int) -> int:
cnt = 1
while self.stack and self.stack[-1][0] <= price: # 单调递减栈
cnt += self.stack.pop()[1]
self.stack.append((price, cnt))
return cnt