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 的值域范围。 ...