Minimum stack ＜ difficulty coefficient ＞

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

Realization MinStack class ( The time complexity of the following interfaces is required to be O(1))：

• MinStack() Initialize stack object .
• void push(int val) Put the element val Push to stack .
• void pop() Delete the element at the top of the stack .
• int top() Get the element at the top of the stack .
• int getMin() Get the smallest element 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.

Tips ：

• -2^31^ <= val <= 2^31^ - 1
• pop、top and getMin Operations are always called on non empty stacks
• push、pop、top、and getMin At most called 3 * 10^4^ Time

🧷 platform ：Visual studio 2017 && windows

The core idea ： Here it does not require us to use arrays or linked lists to implement natively , We use the stack in the library here , Just realize the interface function .

such as 【3, 8, 5, 0 ( Here first push 4 Data , Again pop A data )】, Second, define _min To record the minimum , Every time push Update when conditions are met _min, But when pop I'll put _min Delete the value of , The minimum value at this time is 3, But how do you write to know it's 3, You have to go through all the data in the stack , To know that the minimum value is 3, And at this time pop It is no longer O(1) 了 .

So our correct operation should be given to two stacks , A stack normal value , Another stack minimum ( Note that there are multiple minimum values here ), such as 【3, 8, 5, 0 ( Here first push 4 Data , Again pop A data )】, Here we are going to the first stack push Record the minimum value to the second stack 【3, 0】, If the values in the two stacks pop It's the same , Then all pop,【3】, Or just pop First stack . This is the classic idea of exchanging space for time .

Edge issues , such as 【3, 8, 5, 0 ( Here first push 4 Data , Again pop A data , Again push 0,4,0)】, the last one 0 need push Do you ? The answer is needed , If you don't push, Again pop The minimum value will be deleted ( Because the data at the top of the stack is the same ), here getMin Namely 5, But it's not .

leetcode The original title is

class MinStack {public:    // You don't have to write its constructor here ( Delete it, too ok), because _st and _minst They are all custom types ( Call the default constructor initialization ), At the same time, there is no need to implement the destructor ( Call the default destructor ( Deconstruction of stack )), Similarly, copy construction and assignment do not need .    MinStack() {    }        void push(int val) {        _st.push(val);        // Update stack         if(_minst.empty() || val <= _minst.top())        {            _minst.push(val);        }    }        void pop() {        //_st must pop, The same is all pop        if(_st.top() == _minst.top())        {            _minst.pop();        }        _st.pop();    }        int top() {        return _st.top();    }        int getMin() {        //_minist The top of the stack is the current _st The minimum value of          return _minst.top();    }    stack<int> _st;    stack<int> _minst;};/** * 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(); */