跳到主要内容

栈算法练习

栈（Stack）遵循后进先出（LIFO）原则。常用于括号匹配、逆波兰表达式。进阶面试考点主要包括单调栈（Monotonic Stack）的应用。

20. 有效的括号 (Valid Parentheses)​

题目描述​

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

解题思路​

使用栈辅助。遍历字符串，遇到左括号入栈，遇到右括号弹栈并判断是否匹配。注意最后栈应为空。

Java 代码实现​

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(') stack.push(')');
            else if (c == '[') stack.push(']');
            else if (c == '{') stack.push('}');
            else if (stack.isEmpty() || stack.pop() != c) return false;
        }
        return stack.isEmpty();
    }
}

155. 最小栈 (Min Stack)​

题目描述​

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

解题思路​

维护辅助栈。主栈存放数据，辅助栈存放对应时刻的最小值。每次推送时，将当前元素与辅助栈顶较小者入辅助栈。

Java 代码实现​

class MinStack {
    private Stack<Integer> stack = new Stack<>();
    private Stack<Integer> minStack = new Stack<>();
    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) minStack.push(val);
        else minStack.push(minStack.peek());
    }
    public void pop() { stack.pop(); minStack.pop(); }
    public int top() { return stack.peek(); }
    public int getMin() { return minStack.peek(); }
}

394. 字符串解码 (String Decoding)​

题目描述​

给定一个经过编码的字符串，返回它解码后的字符串。编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。

解题思路​

使用两个栈分别辅助存储数字（倍数）和字符串（已拼好的部分）。

Java 代码实现​

class Solution {
    public String decodeString(String s) {
        StringBuilder res = new StringBuilder();
        int multi = 0;
        Stack<Integer> stack_multi = new Stack<>();
        Stack<String> stack_res = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '[') {
                stack_multi.push(multi); stack_res.push(res.toString());
                multi = 0; res = new StringBuilder();
            } else if (c == ']') {
                StringBuilder tmp = new StringBuilder();
                int curMulti = stack_multi.pop();
                for (int i = 0; i < curMulti; i++) tmp.append(res);
                res = new StringBuilder(stack_res.pop() + tmp);
            } else if (Character.isDigit(c)) multi = multi * 10 + (c - '0');
            else res.append(c);
        }
        return res.toString();
    }
}

739. 每日温度 (Daily Temperatures)​

题目描述​

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

解题思路​

单调栈。 维护一个存放下标的单调递减栈。当遇到更高温度时，说明栈顶下标对应的那一天等到了“更高的温度”，结算并弹栈。

Java 代码实现​

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] res = new int[temperatures.length];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < temperatures.length; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int pre = stack.pop(); res[pre] = i - pre;
            }
            stack.push(i);
        }
        return res;
    }
}

84. 柱状图中最大的矩形 (Largest Rectangle in Histogram)​

题目描述​

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。

解题思路​

单调栈。 寻找每个柱子左右第一个比它矮的柱子索引。

  1. 在数组两端加上高度为 0 的哨兵。
  2. 维护一个单调递增栈。当高度由于变矮而导致不满足递增时，说明栈顶柱子找到了右边界。

Java 代码实现​

class Solution {
    public int largestRectangleArea(int[] heights) {
        int[] h = new int[heights.length + 2];
        System.arraycopy(heights, 0, h, 1, heights.length);
        Stack<Integer> stack = new Stack<>();
        int res = 0;
        for (int i = 0; i < h.length; i++) {
            while (!stack.isEmpty() && h[i] < h[stack.peek()]) {
                int cur = stack.pop();
                res = Math.max(res, h[cur] * (i - stack.peek() - 1));
            }
            stack.push(i);
        }
        return res;
    }
}