242 h155 最小栈

题解

本题本质是一道滑动窗口题
入窗规则:后进栈的元素一定先出栈,所以后进栈元素如果不大于栈顶元素,在其出站前,它前面的元素一定不可能是最小元素

    // 242 h155 最小栈

    static class MinStack {
         Deque<Integer> stack;
        Deque<Integer> currMinValues; //存储某一势力范围最小值
        public MinStack() {
            this.stack=new ArrayDeque<>();
            this.currMinValues=new ArrayDeque<>();
        }

        public void push(int val) {
            // 入栈  1. 元素放入栈顶  2. 辅助栈如果不为空,清出所有比我小的元素,我入栈
            stack.push(val);
            if (currMinValues.isEmpty()||(currMinValues.peek()>=val)){ //不能等于,等于的话就进入别人势力范围
                currMinValues.push(val);
            }

        }

        public void pop() {
            Integer pop = stack.pop();
            if (currMinValues.peek().equals(pop)){
                currMinValues.pop();
            }
        }

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

        public int getMin() {
            return currMinValues.peek();
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34