LeetCode Hot 100 栈系列笔记

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例：

输入：s = "()[]{}"
输出：true

输入：s = "([)]"
输出：false

解题思路：

这道题可以说是栈最经典的入门应用了。核心思想就是利用栈 “后进先出” 的特性，来完美匹配括号的嵌套关系。

整个解法很简单：

1. 遍历整个字符串，当我们遇到一个左括号 (, [, { 时，就把它压入栈中。这相当于是在“存档”，期待后面能有一个对应的右括号来把它“消掉”。
2. 当我们遇到一个右括号时，就从栈顶取出一个元素。如果这时候栈是空的（说明右括号多了），或者取出的左括号和当前右括号不匹配，那整个字符串就肯定不合法了。
3. 遍历结束后，如果栈是空的，说明所有的左括号都被成功匹配了，字符串有效；反之，如果栈里还有“存货”，说明有左括号没找到“另一半”，字符串无效。

代码：

Java

class Solution {
    public boolean isValid(String s) {
        // Deque是双端队列，这里我们用它来实现栈的功能，比Stack性能更好
        Deque<Character> stack = new ArrayDeque<>();

        // 遍历字符串中的每一个字符
        for (char c : s.toCharArray()) {
            if (c == '(') stack.push(')');
            else if (c == '[') stack.push(']');
            else if (c == '{') stack.push('}');
            // 遇到右括号时，如果栈为空或栈顶不匹配，则无效
            else if (stack.isEmpty() || c != stack.pop()) return false;
        }
        
        // 遍历结束后，如果栈为空，说明所有括号都成功匹配
        return stack.isEmpty();
    }
}

（我稍微优化了下你的代码逻辑，使其更简洁，但核心思想完全一致。）

155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

解题思路：

这道题要求我们在实现一个普通栈的基础上，增加一个 getMin 功能，并且所有操作都必须是 O(1) 时间复杂度。

只用一个栈肯定不行，因为当最小值被弹出后，我们很难快速找到下一个最小值。所以，这题的关键在于 “空间换时间”。

我们可以用一个额外的“辅助栈”（min_stack），这个栈的栈顶永远保存着当前主栈中所有元素的最小值。

• push(val):
  • 主栈 stack 正常 push。
  • 对于辅助栈 min_stack，只有当 val 小于或等于其栈顶元素时，才将 val 压入。这样就能保证 min_stack 的栈顶始终是全局最小的。
• pop():
  • 主栈 stack 正常 pop。
  • 检查弹出的这个值，如果它恰好和 min_stack 的栈顶元素相等，说明我们把当前的最小值给弹掉了。那么 min_stack 也需要 pop，来“暴露”出下一个（之前的次小）最小值。

代码：

Java

class MinStack {
    private Stack<Integer> stack;     // 主栈，用于存放所有元素
    private Stack<Integer> min_stack; // 辅助栈，栈顶永远是当前主栈中的最小元素

    public MinStack() {
        stack = new Stack<>();
        min_stack = new Stack<>();
    }

    public void push(int val) {
        // 主栈直接推入新元素
        stack.push(val);
        // 如果辅助栈为空，或者新元素小于等于辅助栈的栈顶元素
        if (min_stack.isEmpty() || val <= min_stack.peek()) {
            // 那么这个新元素也需要压入辅助栈
            min_stack.push(val);
        }
    }

    public void pop() {
        // 主栈弹出元素
        int poppedValue = stack.pop();
        // 如果弹出的元素恰好是当前最小值（即辅助栈的栈顶）
        if (!min_stack.isEmpty() && poppedValue == min_stack.peek()) {
            // 那么辅助栈也需要弹出，以更新最小值
            min_stack.pop();
        }
    }

    public int top() {
        // 返回主栈的栈顶元素
        return stack.peek();
    }

    public int getMin() {
        // 返回辅助栈的栈顶元素，即为当前最小值
        return min_stack.peek();
    }
}

739. 每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

解题思路：

这是一道典型的 单调栈 题目。单调栈，顾名思义，就是栈内元素始终保持单调（在这里是单调递减）的栈。

我们要找的是“右边第一个比我大的数”。可以从后往前遍历温度数组，并用一个栈来维护一个单调递减（从栈顶到栈底）的温度序列的下标。

1. 从后往前遍历，对于当前温度 temperatures[i]：
2. 查看栈顶元素（下标）对应的温度。如果它比当前温度小或相等，说明它绝对不可能成为 i 左边任何一天的“下一个更高温度”（因为 i 更近且温度可能更高），所以直接把它 pop 出去。
3. 重复上一步，直到栈为空或者栈顶温度大于当前温度。
4. 此时，如果栈为空，说明 i 后面没有比它更热的天了，结果是 0。如果栈不为空，那么栈顶的下标就是 i 右边第一个比它热的天的下标，二者相减就是等待天数。
5. 最后，把当前天的下标 i 压入栈中，供前面的元素进行比较。

代码：

Java

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        // 单调栈，里面存储的是数组的下标，而不是温度值
        Stack<Integer> s = new Stack<>();
        int[] res = new int[n];

        // 从后向前遍历数组
        for (int i = n - 1; i >= 0; i--) {
            // 当栈不为空，且当前温度大于等于栈顶下标所对应的温度时
            while (!s.isEmpty() && temperatures[i] >= temperatures[s.peek()]) {
                // 将栈顶元素弹出，因为它对于i之前的元素来说，不是一个“更高”的温度
                s.pop();
            }

            // 循环结束后，如果栈为空，说明后面没有比当前温度更高的了
            // 否则，栈顶的下标就是第一个比当前温度高的日子
            res[i] = s.isEmpty() ? 0 : s.peek() - i;

            // 将当前日期的下标压入栈中，供前面的日期使用
            s.push(i);
        }

        return res;
    }
}

84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例:

输入：heights = [2,1,5,6,2,3]
输出：10

解题思路：

这道题也是单调栈的经典应用，比上一题稍微复杂一些。

核心思想是：遍历每一个柱子，以它为高度，找到它能向左和向右延伸的最大宽度，然后计算面积，最后取所有面积的最大值。

这个“最大宽度”怎么找呢？

• 左边界：从当前柱子向左，找到第一个比它矮的柱子。
• 右边界：从当前柱子向右，找到第一个比它矮的柱子。

问题就转化成了，如何高效地为每个柱子找到它左、右两边第一个更矮的柱子。这正是单调栈的用武之地！

我们可以用三次遍历来解决：

1. 第一次遍历（从左到右）：使用单调栈，为每个柱子 i 找到左边第一个比 heights[i] 矮的柱子下标，存入 left 数组。
2. 第二次遍历（从右到左）：清空并复用单调栈，为每个柱子 i 找到右边第一个比 heights[i] 矮的柱子下标，存入 right 数组。
3. 第三次遍历：根据 left 和 right 数组，计算以每个柱子 i 为高的矩形面积 heights[i] * (right[i] - left[i] - 1)，并更新全局最大值。

代码：

Java

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        // 单调栈，用于寻找边界
        Stack<Integer> s = new Stack<>();

        // left[i] 存储 heights[i] 左边第一个比它矮的柱子的下标
        int[] left = new int[n];
        // right[i] 存储 heights[i] 右边第一个比它矮的柱子的下标
        int[] right = new int[n];

        // 第一次遍历：从左到右，确定每个柱子的左边界
        for (int i = 0; i < n; i++) {
            // 如果栈顶元素对应的高度大于等于当前高度，说明栈顶不是左边界，弹出
            while (!s.isEmpty() && heights[s.peek()] >= heights[i]) {
                s.pop();
            }
            // 此时栈顶就是左边第一个更矮的元素，如果栈为空说明左边没有更矮的
            left[i] = s.isEmpty() ? -1 : s.peek();
            // 当前下标入栈
            s.push(i);
        }
        
        // 清空栈，准备下一次遍历
        s.clear();

        // 第二次遍历：从右到左，确定每个柱子的右边界
        for (int i = n - 1; i >= 0; i--) {
            // 如果栈顶元素对应的高度大于等于当前高度，说明栈顶不是右边界，弹出
            while (!s.isEmpty() && heights[s.peek()] >= heights[i]) {
                s.pop();
            }
            // 此时栈顶就是右边第一个更矮的元素，如果栈为空说明右边没有更矮的
            right[i] = s.isEmpty() ? n : s.peek();
            // 当前下标入栈
            s.push(i);
        }

        int max = 0;
        // 第三次遍历：根据左右边界计算最大面积
        for (int i = 0; i < n; i++) {
            // 宽度 = 右边界下标 - 左边界下标 - 1
            int width = right[i] - left[i] - 1;
            max = Math.max(max, heights[i] * width);
        }

        return max;
    }
}