Leetcode-155-minimum stack

# LeetCode-155- Smallest stack

Design a support push ,pop ,top operation , And can retrieve the stack of the smallest elements in a constant time .

• push(x) —— Put the element x Push into the stack .
• pop() —— Delete the element at the top of the stack .
• top() —— Get stack top element .
• getMin() —— Retrieve the minimum elements in the stack .

Example 1：

 Input ：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

 Output ：
[null,null,null,null,-3,null,0,-2]

 explain ：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   -->  return  -3.
minStack.pop();
minStack.top();      -->  return  0.
minStack.getMin();   -->  return  -2.

Copy

Tips ：

• pop、top and getMin The operation is always in Non empty stack On the call .
• If there is no intersection between two linked lists , return null.
• After returning the result , The two lists still have to keep their original structure .
• It can be assumed that there is no cycle in the whole linked list structure .
• The procedure is as satisfying as possible O(n) Time complexity , And only O(1) Memory .

# Their thinking

Method 1、 Two stacks ：

Need a data stack , A minimum stack

The minimum stack always stores the current minimum

stay push While entering the data stack , Judge whether the minimum stack is empty or whether the new value is less than the top value of the minimum stack ,

If less than, add a new value to the minimum stack , If not less than, add to the top of the minimum stack ( That is, the last smallest element ) Enter the minimum stack

When you need to pop When , Pop up the minimum stack and data stack values at the same time

When you need to getMin when , The element at the top of the stack that returns the smallest stack is the current smallest element

When you need to get top when , Returns the top element of the data stack

# Java Code

class MinStack {

    private Stack<Integer> stack_data;
    private Stack<Integer> stack_min;

    /** initialize your data structure here. */
    public MinStack() {
        stack_data = new Stack<>();
        stack_min = new Stack<>();
    }
    
    public void push(int x) {
        stack_data.push(x);
        if(stack_min.size()==0||x<stack_min.peek()){
            stack_min.push(x);
        }else{
            stack_min.push(stack_min.peek());
        }
    }
    
    public void pop() {
        stack_data.pop();
        stack_min.pop();
    }
    
    public int top() {
        return stack_data.peek();
    }
    
    public int getMin() {
        return stack_min.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.getMin();
 */

Copy

# Java Code 2

class MinStack {

    private Deque<Integer> stackData;
    private Deque<Integer> stackMin;

    /** initialize your data structure here. */
    public MinStack() {
        stackData = new LinkedList();
        stackMin = new LinkedList();
        stackMin.push(Integer.MAX_VALUE);
    }
    
    public void push(int val) {
        stackData.push(val);
        stackMin.push(Math.min(val,stackMin.peek()));
    }
    
    public void pop() {
        stackData.pop();
        stackMin.pop();
    }
    
    public int top() {
        return stackData.peek();
    }
    
    public int getMin() {
        return stackMin.peek();
    }
}

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

Copy