likes
comments
collection
share

【算法】栈总结

作者站长头像
站长
· 阅读数 16

一、前言

栈（stack） 是很简单的数据结构，先进后出的逻辑顺序，符合某些问题的特点，比如说函数调用栈。

「栈」最为广泛的一种应用就是作为「递归」「深度优先遍历」「分治算法」的数据结构支持。

  1. 进栈操作：push

【算法】栈总结

  1. 出栈操作：pop

【算法】栈总结

刷题必知操作：

Stack<Integer> st = new Stack<>(); // 创建栈
st.empty(); // 判断栈是否为空
st.push(e); // 进栈操作
st.peek();  // 取栈顶元素，不弹出
st.pop();   // 取栈顶元素，并弹出

二、题目

（1）有效的括号序列（易）

Leetcode 20

题目描述

这个题目说的是，给你一个括号序列，里面包含小括号，中括号和大括号。你要判断这个括号序列是否有效。有效的括号序列要求，每个左括号都必须有一个同类的右括号与它正确配对。另外，空字符串认为是有效的括号序列。

比如说，给你的序列是：
​
()[]{}
​
小括号/中括号/大括号的左右括号都能正确配对，因此这是一个有效的括号序列。
​
再比如说给你的序列是：
​
([)]
​
这里面虽然正好有一对小括号和一对中括号，但它们的顺序不对，括号间无法正确配对，因此这不是一个有效的括号序列。

思路解法

主要思路：遇见左括号就进栈，遇见右括号就出栈。

AC 代码：

public class LeetCode_20 {
    // Time: O(n), Space: O(n), Faster: 98.96%
    public boolean isValidBracketsShort(String s) {
        Stack<Character> stack = new Stack<>();
​
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '(') stack.push(')');
            else if (s.charAt(i) == '[') stack.push(']');
            else if (s.charAt(i) == '{') stack.push('}');
            else if (stack.isEmpty() || s.charAt(i) != stack.pop()) return false;
        }
        return stack.isEmpty();
    }
}

（2）二叉搜索树迭代器（中）

Leetcode 173

题目描述

这个题目说的是，给你一棵二叉搜索树，你要为它实现一个迭代器。迭代器中包含两个公有方法，next() 方法返回二叉搜索树中下一个最小的数字，hasNext() 方法返回是否还存在下一个数字。

注意，next() 方法和 hasNext() 方法都要求平均时间复杂度是 O(1)，并且额外只能使用 O(h) 的辅助空间。其中，h 是二叉搜索树的高度。另外，你可以假设对 next() 方法的调用总是有效的，即不需要考虑在 next() 方法中处理不存在下一个数字的情况。

比如说，给你的二叉搜索树 t 是：
​
t:
    1
  /   \
 0     4
      / \
     2   8
​
用 t 初始化迭代器，然后就可以调用 next() 和 hasNext()：
​
BSTIterator it = new BSTIterator(t);
it.next();    //  0
it.next();    //  1
it.next();    //  2
it.hasNext(); // true
it.next();    //  4
it.next();    //  8
it.hasNext(); // false

思路解法

思路有二： 暴力法 和 辅助栈。

  1. 暴力法：先中序遍历，得到有序数组
class BSTIterator {
    private int idx;
    private List<Integer> arr;
​
    public BSTIterator(TreeNode root) {
        idx = 0;
        arr = new ArrayList<>();
        inorderTraversal(root, arr);
    }
​
    public int next() {
        return arr.get(idx++);
    }
​
    public boolean hasNext() {
        return idx < arr.size();
    }
    // 中序遍历，得到升序的有序数组
    private void inorderTraversal(TreeNode root, List<Integer> arr) {
        if (root == null) {
            return;
        }
        inorderTraversal(root.left, arr);
        arr.add(root.val);
        inorderTraversal(root.right, arr);
    }
}
  1. 辅助栈

主要分两步：

  1. 初始化： 把根节点的左节点递归入栈

  2. next()：

    1. 把栈顶节点出栈，并把节点值返回
    2. 把栈顶节点右子树的最左侧分支入栈

【算法】栈总结

public class BSTIterator {
    private final Stack<TreeNode> stack = new Stack<>();
​
    public BSTIterator(TreeNode root) {
        pushLeft(root);  // 构建时
    }
    
    private void pushLeft(TreeNode node) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
    }
​
    // T(avg): O(1), S(avg): O(h)
    public int next() {
        TreeNode node = stack.pop(); // 1. 把栈顶节点出栈，并把节点值返回
        pushLeft(node.right);        // 2. 把栈顶节点右子树的最左侧分支入栈
        return node.val;
    }
​
    // T(avg): O(1), S(avg): O(h)
    public boolean hasNext() {
        return stack.size() != 0;
    }
​
}

（3）温度升高需要等待的天数（中）

Leetcode 739

题目描述

这个题目说的是，给你一个不为空的整数数组，数组中的元素表示每天的温度。你要计算出，对于每一天来说，温度升高需要等待的天数。如果对于某一天，未来不存在比它更高的温度，就把它对应的等待天数设置为 0。

# 比如说，给你的温度数组是：
1, 3, 1, 3, 2, 6
​
# 对于每一天来说，温度升高需要等待的天数是：
1, 4, 1, 2, 1, 0

说白了就是：比当天的温度高的下一天在哪？

【算法】栈总结

计算公式：j - i

思路解法

思路有三：暴力法、辅助栈 和 跳跃法。

  1. 方法一：暴力法

2 层 for 循环。

public class LeetCode_739 {
    // Time: O(n ^ 2), Space: O(1), Faster: 6.67%
    public int[] dailyTemperatures(int[] temperatures) {
        if (null == temperatures || temperatures.length == 0) return new int[0];
        int [] result = new int[temperatures.length];
        for (int i = 0; i < temperatures.length - 1; ++i) {
            int ans = 0;
            for (int j = i + 1; j < temperatures.length; ++j) {
                if (temperatures[j] > temperatures[i]) {
                    ans = j - i;
                    break;
                }
            }
            result[i] = ans;
        }
        return result;
    }
}
  1. 方法二：辅助栈，递减栈（每个入栈的数比上一个小）

主要逻辑：计算栈里元素

  1. 遍历列表：遍历结束需入栈当前下标

  2. 栈不为空，比较栈顶值 与 当前值

    • 栈顶值 < 当前值：出栈，并计算栈里下标
    • 栈顶值 >= 当前值：入栈

【算法】栈总结

【算法】栈总结

public class LeetCode_739 {
    // 方法二：辅助栈
    // Time: O(n), Space: O(n), Faster: 44.57%
    public int[] dailyTemperaturesStack(int[] temperatures) {
        int n = temperatures.length;
        int[] result = new int[n];
        Stack<Integer> st = new Stack<>();
        for (int i = 0; i < n; ++i) {
            // 栈不为空 且 栈顶值 < 当前值
            while (!st.empty() && temperatures[st.peek()] < temperatures[i]) {
                int idx = st.pop();    // 出栈
                result[idx] = i - idx; // 计算
            }
            st.push(i); // 入栈
        }
        // while (!st.empty()) result[st.pop()] = 0;
        return result;
    }
}
  1. 方法三：跳跃法

暴力解法之所以慢： 在计算某一天时，要去检查它后面所有的温度。

跳跃法： 跳跃比较较大温度即可。有一个步长概念。

步长计算公式：j = j + t(j)  

【算法】栈总结

AC 代码：

public class LeetCode_739 {
    // 方法三：跳跃法
    // Time: O(n), Space: O(1), Faster: 99.98%
    public int[] dailyTemperaturesSkip(int[] temperatures) {
        int n = temperatures.length;
        int[] result = new int[n];
        for (int i = n - 2; i >= 0; --i) {
            int j = i + 1;
            // 1. 跳跃比较
            while (temperatures[j] <= temperatures[i] && result[j] != 0) j += result[j];
            // 2. 计算
            if (temperatures[j] > temperatures[i]) result[i] = j - i;
            // else result[i] = 0;
        }
        return result;
    }
}

（4）直方图中的最大矩形（难）

LeetCode 84

题目描述

题目说的是，给你一个非负整数数组，数组中的整数表示直方图的高度，每个直方图的宽度都为 1，你要计算出直方图中最大矩形的面积。

比如说，给你的数组是 2, 1, 3, 4, 1, 它对应的直方图如图所示：

          +--+
          |  |
       +--+  |
       |  |  |
 +--+  |  |  |
 |  |  |  |  |
 |  +--+  |  +--+
 |  |  |  |  |  |
 +--+--+--+--+--+-->
  2  1  3  4  1

在这些直方图组成的区域里，可以形成的最大矩形是 3 和 4 这两个直方图中，高度为 3，宽度为 2 的矩形。它的面积为 6，因此你要返回 6。

思路解法

思路有三：

  1. 方法一：暴力法：左、右两指针来求宽

    大于等于当前高度的才扩展。

【算法】栈总结

public class LeetCode_84 {

    // 方法一：暴力法, 超时
    // Time: O(n), Space: O(1), Faster: 15.78%
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) return 0;
        int max = 0, n = heights.length;
        for (int i = 0; i < n; ++i) {
            int l = i, r = i;
            // 向左边伸展
            while (l >= 0 && heights[l] >= heights[i]) --l;
            // 向右边伸展
            while (r < n && heights[r] >= heights[i]) ++r;
            max = Math.max(max, heights[i] * (r - l - 1));
        }
        return max;
    }
}
  1. 方法二：辅助栈维护一个下标序列

辅助栈维护一个下标序列，这些下标对应的直方图高度依次递增。

当 r 对应的高度小于栈顶下标对应的高度时，对于栈顶下标对应的高度来说：

  • 指针：下标 r 是它的右边界
  • 栈顶的前一个元素是它的左边界

用图来解释： 【算法】栈总结

  1. 遍历到第 1 个元素： 栈为空，下标 0 直接进栈 【算法】栈总结

  2. 遍历到第 2 个元素： 【算法】栈总结

  3. 遍历到第 3 个元素： 【算法】栈总结

  4. 遍历到第 4 个元素： 【算法】栈总结

  5. 遍历到第 5 个元素： 【算法】栈总结

  6. 遍历到第 6 个元素： 【算法】栈总结

public class LeetCode_84 {
​
    // 方法二：用栈模拟
    // Time: O(n), Space: O(n), Faster: 16.07%
    public int largestRectangleAreaStack(int[] heights) {
        if (heights == null || heights.length == 0) return 0;
        int max = 0, n = heights.length;
        Stack<Integer> st = new Stack<>();
        for (int r = 0; r <= n; ++r) {
            int h = r == n ? 0 : heights[r];
            while (!st.empty() && h < heights[st.peek()]) {
                int idx = st.pop();
                int l = st.empty() ? -1 : st.peek();
                max = Math.max(max, heights[idx] * (r - l - 1));
            }
            st.push(r);
        }
        return max;
    }
}
  1. 方法三：类似方法二，只是用数组代替栈
public class LeetCode_84 {
    // 方法三：用数组模拟栈
    // Time: O(n), Space: O(n), Faster: 99.32%
    public int largestRectangleAreaArray(int[] heights) {
        if (heights == null || heights.length == 0) return 0;
        int max = 0, n = heights.length, top = -1;
        int[] st = new int[n + 1];
        for (int r = 0; r <= n; ++r) {
            int h = r == n ? 0 : heights[r];
            while (top != -1 && h < heights[st[top]]) {
                int idx = st[top--];
                int l = top == -1 ? -1 : st[top];
                max = Math.max(max, heights[idx] * (r - l - 1));
            }
            st[++top] = r;
        }
        return max;
    }
}