题解 | #牛牛的最大栈#

思路

最小栈的变体。使用双栈解决，一个维护原本的栈，一个维护当前最大值的栈。

最大栈的意义在于栈顶就是原始栈的最大值，即栈中的元素是非递减的。

时间复杂度为 ，空间复杂度为 ，其中 表示操作数的大小。

参考代码

import java.util.*;


public class Solution {
    Stack<Integer> stack = new Stack<>();
    Stack<Integer> maxStack = new Stack<>();

    public int[] processStackOperations (String[] operations, int[] values) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < operations.length; i++) {
            if ("push".equals(operations[i])) {
                push(values[i]);
            } else if ("pop".equals(operations[i])) {
                pop();
            } else if ("getMax".equals(operations[i])) {
                list.add(getMax());
            } else if ("top".equals(operations[i])) {
                list.add(top());
            }
        }
        return list.stream().mapToInt(i -> i).toArray();
    }

    private void pop() {
        if (stack.peek() == maxStack.peek()) {
            maxStack.pop();
        }
        stack.pop();
    }

    private void push(int value) {
        if (maxStack.isEmpty() || maxStack.peek() <= value) {
            maxStack.add(value);
        }
        stack.add(value);
    }

    private int getMax() {
        return maxStack.peek();
    }

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