LeetCode 刷题 —— 辅助栈

lalala / 2023-05-14 / 原文

42. 接雨水

class Solution {
    public int trap(int[] height) {
        int res = 0;
        Stack<Integer> leftWallStack = new Stack();
        int len = height.length;
        leftWallStack.push(0);
        for (int i=1;i<len;i++) {
            int rightWallIndex = i;
            int stackTopIndex = leftWallStack.peek();
            // 栈顶元素要当底部，右边出现比栈顶元素高的，那么它就可以顺利当底部。可以出栈了
            while (!leftWallStack.isEmpty() && height[rightWallIndex] > height[stackTopIndex]) {
                 // 出栈
                leftWallStack.pop();
                if (leftWallStack.isEmpty()) {
                    break;
                }
                // 栈的下一个元素要当左边的墙
                int leftWallIndex = leftWallStack.peek();
                // 左边的墙也要比出栈的容器底部高，才可以接到雨水
                if (height[leftWallIndex] > height[stackTopIndex]) {
                    int h = Math.min(height[leftWallIndex], height[rightWallIndex]) - height[stackTopIndex];
                    int w = rightWallIndex - leftWallIndex - 1;
                    res = res + h*w;
                }
                stackTopIndex = leftWallIndex;
            }
            // 不管怎么样，用来比较的右边新元素每次都要入栈
            leftWallStack.push(i);
        }
        return res;
    }

剑指 Offer 30. 包含min函数的栈

用一个辅助栈 minStack，记录当前最小的元素

push: 如果当前加入的元素比 minStack 的小【或等于，为什么要有等于看代码注释】，就把这个元素也 push 进入 minStack

pop: 从主栈弹出，如果主栈弹出的这个元素和 minStack 相等，说明这个最小的已经走了，minStack 也要 pop 弹出

top：主栈的栈顶（peek）

min: 辅助栈 minStack 的栈顶（peek）

class MinStack {

    private Stack<Integer> mainStack;

    private Stack<Integer> minStack;

    /** initialize your data structure here. */
    public MinStack() {
        mainStack = new Stack();
        minStack = new Stack();
    }
    
    public void push(int x) {
        mainStack.push(x);
        if (minStack.isEmpty()) {
            minStack.push(x);
        }
        // minStack 放的是当前最小，因此只有新入的元素比 minStack 栈顶小，才入栈
        // 一定要注意这里要加 = 否则有重复最小元素，只入栈了一个的话，那 pop 的时候这个出栈，之后 minStack.peek() 就会报错 
        else if (x <= minStack.peek()) {
            minStack.push(x);
        }
    }
    
    public void pop() {
        int top = mainStack.pop();
        // 主栈出栈的时候，如果 minStack 栈顶与主栈栈顶相同，它也要出栈
        if (top == minStack.peek()) {
            minStack.pop();
        }
    }
    
    public int top() {
        return mainStack.peek();
    }
    
    public int min() {
        return minStack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */