跳到主要内容

栈

栈常用于处理具有后进先出 (LIFO) 特性的场景，如匹配括对、简化路径、递归迭代转换等。

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

题目描述​

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

有效字符串需满足：

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

解题思路​

辅助栈 + 哈希映射。

  1. 遍历字符串。
  2. 遇到左括号，入栈。
  3. 遇到右括号，出栈一个元素检查是否匹配。如果不匹配直接 false。
  4. 最后检查栈是否为空。

Java 代码实现​

class Solution {
    public boolean isValid(String s) {
        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() || stack.pop() != c) return false;
        }
        return stack.isEmpty();
    }
}

71. 简化路径 (Simplify Path)​

题目描述​

给你一个字符串 path ，表示一个绝对路径（以 '/' 开头）。请你将其转换为更加简洁的 规范路径 。

在 Unix 风格的文件系统中，规则如下：

  • 一个点 '.' 表示当前目录本身。
  • 两个点 '..' 表示将目录切换到上一级（指向父目录）。
  • 任意多个连续的斜杠（即 '//'）都被视为单个斜杠 '/' 。
  • 任意其他字符序列（如 'abc'）都被视为目录名称。

规范路径 应遵循下述格式：

  • 始终以斜杠 '/' 开头。
  • 两个目录名之间必须只有一个斜杠 '/' 。
  • 最后一个目录名（如果存在）不能 以斜杠 '/' 结尾。
  • 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。

返回简化后的 规范路径 。

解题思路​

分割 + 栈筛选。

  1. 使用 / 分割路径，得到单词列表。
  2. 遇到 ".." 时，如果栈不为空则弹出栈顶（回退一级）。
  3. 遇到 "." 或 ""（多余的斜杠产生的空串）时，不做任何操作。
  4. 其他普通文件名，压入栈中。
  5. 最后将栈中的文件名以 / 拼接。

Java 代码实现​

class Solution {
    public String simplifyPath(String path) {
        Deque<String> stack = new ArrayDeque<>();
        for (String s : path.split("/")) {
            if (s.equals("..")) {
                if (!stack.isEmpty()) stack.pop();
            } else if (!s.equals("") && !s.equals(".")) {
                stack.push(s);
            }
        }
        if (stack.isEmpty()) return "/";
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) sb.append("/").append(stack.pollLast());
        return sb.toString();
    }
}

155. 最小栈 (Min Stack)​

题目描述​

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

实现 MinStack 类:

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

解题思路​

同步辅助栈。

  1. 维护一个数据栈 dataStack 和一个最小栈 minStack。
  2. push(x)：数据栈压入 x。最小栈压入 min(x, minStack.peek())。
  3. pop()：两栈同步弹出。
  4. getMin()：直接返回最小栈栈顶。

Java 代码实现​

class MinStack {
    Deque<Integer> stack = new ArrayDeque<>();
    Deque<Integer> minStack = new ArrayDeque<>();

    public MinStack() {
        minStack.push(Integer.MAX_VALUE);
    }

    public void push(int val) {
        stack.push(val);
        minStack.push(Math.min(val, minStack.peek()));
    }

    public void pop() {
        stack.pop();
        minStack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

150. 逆波兰表达式求值 (Evaluate Reverse Polish Notation)​

题目描述​

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

  • 有效的算符为 '+'、'-'、'*' 和 '/' 。
  • 每个操作数（每个 token）都可以是一个整数或者另一个表达式。
  • 两个整数之间的除法总是 向零取整 。
  • 输入的逆波兰表达式总是有效的。这意味着表达式总会得出有效数值且不存在除数为 0 的情况。

解题思路​

栈处理后缀表达式。

  1. 遍历表达式数组。
  2. 如果是数字，压入栈。
  3. 如果是运算符，弹出两个数进行运算（注意顺序：第二个出的数为左操作数），结果再次入栈。

Java 代码实现​

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (String s : tokens) {
            if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
                int b = stack.pop(), a = stack.pop();
                if (s.equals("+")) stack.push(a + b);
                else if (s.equals("-")) stack.push(a - b);
                else if (s.equals("*")) stack.push(a * b);
                else stack.push(a / b);
            } else {
                stack.push(Integer.parseInt(s));
            }
        }
        return stack.pop();
    }
}

224. 基本计算器 (Basic Calculator)​

题目描述​

给你一个字符串 s ，表示一个有效的算术表达式，计算并返回结果。

注意： 不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

解题思路​

符号记录器 + 栈保存状态。

  1. 维护 res（当前累计和）和 sign（当前正负号）。
  2. 遇到 ( 时，将之前的 res 和 sign 压入栈，重置 res。
  3. 遇到 ) 时，弹出之前的 sign 和 res 进行结合。
  4. 遇到数字时进行解析累加。

Java 代码实现​

class Solution {
    public int calculate(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        int res = 0, sign = 1, n = s.length();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int val = c - '0';
                while (i + 1 < n && Character.isDigit(s.charAt(i + 1))) val = val * 10 + (s.charAt(++i) - '0');

                res += sign * val;
            } else if (c == '+') sign = 1;
            else if (c == '-') sign = -1;
            else if (c == '(') {
                stack.push(res);
                stack.push(sign);
                res = 0; sign = 1;
            } else if (c == ')') {
                res = stack.pop() * res + stack.pop();
            }
        }
        return res;
    }
}

Wait, I see a bug in the code I just wrote (Character.isDigit check). Fixing it. Actually, the calculation loop for digits: while (i + 1 < n && Character.isDigit(s.charAt(i + 1))) val = val * 10 + (s.charAt(++i) - '0'); Let's update the content.