155. Min Stack

发表于 | 分类于 ， | 阅读次数:

Total Accepted: 61492
Total Submissions: 286112
Difficulty: Easy

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  • push(x) – Push element x onto stack.

  • pop() – Removes the element on top of the stack.

  • top() – Get the top element.

  • getMin() – Retrieve the minimum element in the stack.

Java:

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
class MinStack {
    Stack<Integer> stack=new Stack<Integer>();
    int min=Integer.MAX_VALUE;
    public void push(int x) {
        if(x<=min){
            //save the last min element
            stack.push(min);
            min=x;
        }
        stack.push(x);
    }

    public void pop() {
        if(min==stack.pop()){
            min=stack.peek();
            stack.pop();
        }
        if(stack.empty())
            min=Integer.MAX_VALUE;
    }

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

    public int getMin() {
        return min;
    }
}

打个小广告

欢迎加入我的小专栏「基你太美」一起学习。