概念 & 应用

通常是一维数组，要寻找任一个元素的右边/左边第一个比自己大/小的元素的位置，此时我们就要想到可以用单调栈了。

单调栈的本质是空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素（大/小）的元素，优点是只需要遍历一次。

单调栈何时用

为任意一个元素找左边和右边第一个比自己大/小的位置，用单调栈

用递增单调栈 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]

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

---

---