栈的经典算法应用：LeetCode 精选题目解析

三、227.基本计算器 II

题目描述：

给我们一个字符串，其中只包含加减乘除和数字和空格几种字符。返回按照数学运算，计算后的数字，这个数字不会超过 int 范围。

解题思路：

• 整体思路：将所有的运算符变成加。
• 我们只需要将每个数字前面的运算符使用运算符变量记录下来。
• 当遍历到字符为空格就向后走。
• 遍历到是运算符，就将运算符变量更新为这个运算符，向后走。
• 遍历到数字，我们使用变量记录下来，再向后遍历看是不是数字，因为在这道题中 123 这种是三个字符连在一堆表示。
• 当变量存储完之后，看前面的运算符变量是什么，是减，就将相反数入栈，是加，直接入栈，是乘和除，就拿栈顶元素进行运算后再入栈。
• 最后将栈中的元素加起来就是结果了。

解题代码：

// 时间复杂度：O(n)
// 空间复杂度：O(n)
class Solution {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<>();
        char op = '+';
        int i = 0;
        while (i < s.length()) {
            if (s.charAt(i) == ' ') {
                i++;
            } else if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                int tmp = 0;
                while (i < s.length() && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                    tmp = tmp * 10 + (s.charAt(i) - '0');
                    i++;
                }
                if (op == '+') stack.push(tmp);
                if (op == '-') stack.push(-tmp);
                if (op == '*') stack.push(stack.pop() * tmp);
                if (op == '/') stack.push(stack.pop() / tmp);
            } else {
                op = s.charAt(i);
                i++;
            }
        }
        int ret = 0;
        while (!stack.isEmpty()) {
            ret += stack.pop();
        }
        return ret;
    }
}

四、394.字符串解码

题目描述：

中括号中的字符要重复中括号前面的数字倍。数字只会作为倍数出现。

解题思路：

• 我们遍历字符串会出现四种情况：字母（指不被中括号包含的）、数字、左括号 '['、右括号 ']'。
• 我们要将数字与数字对应要重复的字符串对应起来，所以我们使用两个栈分别储存数字和字符串。
• 遇到数字的时候，我们就将数字提取出来，放入数字栈中。使用循环遍历拿到每个数字字符（不用注意越界），加在个位即可。
• 遇到左括号 '[' 时，我们就将左括号和右括号中包含的字符串（不用注意越界因为一定有']'）放入栈顶。
• 遇到右括号 ']' 时，我们就拿去两个栈的栈顶元素，重复字符串，拼接在现在的栈顶元素后。
• 遇到字母（指不被中括号包含的）时，拿取这个字符串（此时需要注意越界问题），拼接在现在的栈顶元素后。
• 因为有拼接在栈顶元素，如果字符串开始时就是字母（指不被中括号包含的），那么会空指针异常，所以在一开始的字符串栈就填入一个空串。

解题代码：

// 时间复杂度：O(n)
// 空间复杂度：O(n)
class Solution {
    public String decodeString(String s) {
        Stack<StringBuffer> stackString = new Stack<>();
        stackString.push(new StringBuffer());
        Stack<Integer> stackInt = new Stack<>();
        int cur = 0;
        while (cur < s.length()) {
            if (s.charAt(cur) >= '0' && s.charAt(cur) <= '9') {
                // 数字
                int tmp = 0;
                while (s.charAt(cur) >= '0' && s.charAt(cur) <= '9') {
                    tmp = tmp * 10 + (s.charAt(cur++) - '0');
                }
                stackInt.push(tmp);
            } else if (s.charAt(cur) == '[') {
                // 左括号
                cur++;
                StringBuffer tmp = new StringBuffer();
                while (s.charAt(cur) >= 'a' && s.charAt(cur) <= 'z') {
                    tmp.append(s.charAt(cur++));
                }
                stackString.push(tmp);
            } else if (s.charAt(cur) == ']') {
                // 右括号
                cur++;
                int k = stackInt.pop();
                StringBuffer tmp = stackString.pop();
                while (k-- != 0) {
                    stackString.peek().append(tmp);
                }
            } else {
                // 字母（指不被中括号包含的）
                while (cur < s.length() && s.charAt(cur) >= 'a' && s.charAt(cur) <= 'z') {
                    stackString.peek().append(s.charAt(cur++));
                }
            }
        }
        return stackString.peek().toString();
    }
}

五、946.验证栈序列

题目描述：

看 popped 数组是不是按照 pushed 数组元素入栈顺序能拿到的顺序。

解题思路：

• 遍历 pushed 数组，元素入栈，如果 pushed 数组元素与当前 popped 数字的当前下标元素不同，就入栈。
• pushed 数组元素与当前 popped 数字的当前下标元素相同，就出栈直到栈顶元素与 popped 数字的当前下标元素不同或者栈空为止。
• 最后如果栈还有元素，那么就返回 false，反之，返回 true。

解题代码：

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int cur = 0; // popped 当前访问的下标
        for (int i = 0; i < pushed.length; i++) {
            if (pushed[i] != popped[cur]) {
                stack.push(pushed[i]);
            } else {
                stack.push(pushed[i]);
                while (!stack.isEmpty() && stack.peek() == popped[cur]) {
                    stack.pop();
                    cur++;
                }
            }
        }
        return stack.isEmpty();
    }
}