Leetcode points to offer 30 Stack containing min function

The finger of the sword Offer 30. contain min Function of the stack

difficulty Simple

Defines the data structure of the stack , Please implement a in this type that can get the minimum elements of the stack min The function is in the stack , call min、push And pop The time complexity of O(1).

Example :

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

Tips ：

1. The total number of calls to each function shall not exceed 20000 Time

Answer key

​ This problem is to design a minimum stack , It has one more function than stack Min, How to design this function , I think the simpler thing is to design a stack of the same size , This stack mainly records the minimum value from the front to the present , Stack together .

​ For example, the example given

​ [“MinStack”,“push”,“push”,“push”,“min”,“pop”,“top”,“min”]

​ [[],[-2],[0],[-3],[],[],[],[]]

​ Three times push When , The two stacks are [-3, 0, -2] and [-3, -2, -2], The second is the minimum stack , Record the minimum value from the beginning to the present , such min The time complexity is O(1) 了

​ There is also a hole pop function , Because of joining min After the stack , If the smallest element pops up , We don't update min The value will appear bug, Such as now min There is... In the stack [-20, -10, 0], When we pop up -20, Recompression -14 When , If the previous stack is not updated min value , So this -14 It's like a stack , And pressed in -20.（ These are code logic problems , Especially when designing multiple objects , Be sure to pay attention to logic , Otherwise there will be unexpected bug）

class MinStack {
    
    Deque<Integer> deque;// Stack 
    Deque<Integer> minDeque;//min Stack 
    int min = Integer.MAX_VALUE;//min value 

    /** initialize your data structure here. */
    public MinStack() {
    // initialization 
        deque = new ArrayDeque<Integer>();
        minDeque = new ArrayDeque<Integer>();
    }
    
    public void push(int x) {
    
        deque.push(x);// Push 
        min = Math.min(min, x);// Compare the minimum 
        minDeque.push(min);// The minimum value is put on the stack 
    }
    
    public void pop() {
    
        if(!deque.isEmpty()){
    // The queue is not empty 
            deque.removeFirst();// Because it uses a double ended queue deque,push It's to be put at the head of the team , namely first Location , So what pops up is first
            minDeque.removeFirst();
            if(!minDeque.isEmpty()){
    //min Stack is not empty. 
                min = minDeque.getFirst();// Stack update min value 
            }else{
    
                min = Integer.MAX_VALUE;// When min When the stack is empty , Update to maximum , Avoid using old values next time 
            }
        }
    }
    
    public int top() {
    
        return deque.getFirst();
    }
    
    public int min() {
    
        return minDeque.getFirst();
    }
}

/** * 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.min(); */