155. Min Stack

Posted on Edited on

题目

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.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); –> Returns -3.
minStack.pop();
minStack.top(); –> Returns 0.
minStack.getMin(); –> Returns -2.

思路

题目要求在O(1)时间内实现，所以用一个Stack应该是不可能的，于是这题应该是用两个Stack，一个当做正常的Stack，一个专门用来储存最小值。

不过后面看了Discuss，有人用一个栈就做出来了……

代码

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
35
36
37
38
//C++ Solution
class MinStack {
    /** initialize your data structure here. */
private:
    stack<int> nor;
    stack<int> min;
public: 
    void push(int x) {
        if(min.empty()||x<=min.top()) {
            min.push(x);
        }
        nor.push(x);
    }
    
    void pop() {
        if(nor.top()==min.top()) {
            min.pop();
        }
        nor.pop();
    }
    
    int top() {
        return nor.top();
    }
    
    int getMin() {
        return min.top();
    }
};

/**
 * 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.getMin();
 */
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
//Java Solution
class MinStack {

    /** initialize your data structure here. */
    Stack<Integer> nor = new Stack<>();
    Stack<Integer> min = new Stack<>();
    public MinStack() {
        
    }
    
    public void push(int x) {
        if(min.isEmpty()||x<=min.peek()) {
            min.push(x);
        }
        nor.push(x);
    }
    
    public void pop() {
        if(nor.peek() == min.peek()) { min.pop();}
        nor.pop();
    }
    
    public int top() {
        return nor.peek();
    }
    
    public int getMin() {
        return min.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
35
36
37
38
39
40
public class MinStack {
    long min;
    Stack<Long> stack;

    public MinStack(){
        stack=new Stack<>();
    }
    
    public void push(int x) {
        if (stack.isEmpty()){
            stack.push(0L);
            min=x;
        }else{
            stack.push(x-min);//Could be negative if min value needs to change
            if (x<min) min=x;
        }
    }

    public void pop() {
        if (stack.isEmpty()) return;
        
        long pop=stack.pop();
        
        if (pop<0)  min=min-pop;//If negative, increase the min value
        
    }

    public int top() {
        long top=stack.peek();
        if (top>0){
            return (int)(top+min);
        }else{
           return (int)(min);
        }
    }

    public int getMin() {
        return (int)min;
    }
}