单调栈

LeetCode 316 https://leetcode.cn/problems/remove-duplicate-letters/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 单调栈。 统计每个字母的出现次数，记到一个哈希表或者数组 left 中。 遍历 s，先把 left[s[i]] 减一。 如果 s[i] 在 ans 中，直接 continue。为了快速判断 s[i] 是否在 ans 中，可以用一个哈希表或者布尔数组 inAns 辅助判断。 如果 s[i] 不在 ans 中，那么判断 s[i] 是否小于 ans 的最后一个字母（记作 x），如果 s[i]<x 且 left[x]>0，那么可以把 x 从 ans 中去掉，同时标记 inAns[x]=false。 反复执行第 4 步，直到 ans 为空，或者 s[i]>x，或者 left[x]=0。 把 s[i] 添加到 ans 末尾，同时标记 inAns[s[i]]=true。然后继续遍历 s 的下一个字母。 遍历完 s 后，返回 ans。 时间复杂度：O(n)，其中 n 为 s 的长度。我们写了一个二重循环，看上去是 O(n^2) 的，但是考虑到每个 s[i] 加到 ans 中至多一次，从 ans 中去掉也至多一次。所以整体上看，算法的时间复杂度是 O(n) 的。 空间复杂度：O(∣Σ∣)，其中 ∣Σ∣ 为字符集的大小，本题中字符均为小写字母，所以 ∣Σ∣=26。注意 ans 的长度不会超过 ∣Σ∣。 ...

LeetCode 84 https://leetcode.cn/problems/largest-rectangle-in-histogram/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 单调栈。h = height[i]，left[i] 表示在 i 左侧小于 h 的最近元素下标，right[i] 表示在 i 右侧小于等于 h 的最近元素下标。以 h 为高度的矩形的最大面积为 height[i] * (right[i] - left[i] - 1)。 两次遍历，在计算 left 的过程中，如果栈顶元素 ≥ heights[i]，那么 i 就是栈顶元素的 right。 时间复杂度：O(n)，其中 n 为 heights 的长度。每个元素入栈出栈各至多一次，所以二重循环是 O(n) 的。 空间复杂度：O(n)。 ...

LeetCode 85 https://leetcode.cn/problems/maximal-rectangle/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题是 LeetCoce 84 柱状图中最大的矩形的升级版，枚举矩形的底边，做 m 次 largestRectangleArea。如果 matrix[i][j]=0，那么没有柱子，高度等于 0。否则，在上一行柱子的基础上，把柱子高度增加 1。 时间复杂度：O(mn)，其中 m 和 n 分别为 matrix 的行数和列数。做 m 次 84 题，每次 O(n)。 空间复杂度：O(n)。 ...

LeetCode 402 https://leetcode.cn/problems/remove-k-digits/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题需要尽量保证前面的数字最小，这可以使用单调栈来实现。 我们定义一个单调栈，遍历整个数字，当 k > 0 时，对于当前数字，判断是否小于栈顶，否则弹出栈顶元素。这样最后从栈底到栈顶单调不减。 如果最后 k 还是 > 0，那么直接删除最后的 k - m 个元素，因为他们是最大的。 为了生成答案，需要从栈底到栈顶遍历，因此栈使用 vector 来实现。 时间复杂度：O(n)，其中 n 为字符串的长度。 空间复杂度：O(n)。栈存储数字需要线性的空间。 ...

LeetCode 739 https://leetcode.cn/problems/daily-temperatures/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 单调栈经典题目。从左往右遍历，栈中记录还没算出下一个更大元素的那些数的下标。相当于栈是一个 todolist，在循环的过程中，现在还不知道答案是多少，在后面的循环中会算出答案。 时间复杂度：O(n)，其中 n 为 temperatures 的长度。虽然我们写了个二重循环，但站在每个元素的视角看，这个元素在二重循环中最多入栈出栈各一次，因此循环次数之和是 O(n)，所以时间复杂度是 O(n)。 空间复杂度：O(n)。注意这种写法栈中可以有重复元素。 ...

LeetCode 42 https://leetcode.cn/problems/trapping-rain-water/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题为常考的 Hard 题目，有多种做法，分别是前后缀分解，相向双指针和单调栈。本文使用单调栈方法。单调栈的做法相当于「横着」计算面积。 这个方法可以总结成 16 个字：找上一个更大元素，在找的过程中填坑。 如果当前元素大于栈顶元素，栈顶元素作为底边，当前元素作为右边，再找栈中第二小的元素作为左边。这段区域可以接的水为 min(height[left], height[i]) - bottom_h * (i - left - 1)。如果找不到第二小的元素，说明这一段不能接水。最后将 i 入栈。 时间复杂度：O(n)，其中 n 为 height 的长度。虽然我们写了个二重循环，但站在每个元素的视角看，这个元素在二重循环中最多入栈出栈各一次，因此循环次数之和是 O(n)，所以时间复杂度是 O(n)。 空间复杂度：O(min(n,U))，其中 U=max(height)−min(height)+1。注意栈中没有重复元素，在 height 值域很小的情况下，空间复杂度主要取决于 height 的值域范围。 ...