AcWing 41. Stack containing min function (monotone stack)

Pre knowledge ： Monotonic stack

The question ：

The topic should be in O(1) All the operations described in the question can be realized within the time of .

Ideas ：

In order to O(1) Time complexity of Realization getMin() operation , We also need to maintain another auxiliary stack B（ Monotonic stack ）, Stack B Is stored in Original stack A The minimum value of each piece of data starting at the bottom of the stack in the , The element has monotonicity .

How to maintain Monotonic stack Well ,

• push ： When we go to the stack Push the A few hours , If This number ≤ The top element of a monotonic stack , Then the number At the same time, press into the monotone stack ; otherwise , Do not press in , This is because the stack has First in, then out nature , therefore ： In this number Before being ejected , In the stack There is always a number smaller than this number , therefore This number must not be taken as the minimum number Output .

• pop ： When we get out of the stack eject A few hours , If This number is equal to the top element of the monotone stack , be At the same time, pop up the top element of the monotone stack .

Monotone stack because of its monotonicity , So its top element , Is the minimum number in the current stack .（ This topic realizes O(1) The key to complexity ）

Be careful ：

• When pushing an element onto a monotone stack , The number must be “ Less than or equal to ” Monotone stack top element , Instead of “ Less than ” , namely The number of elements equal to the top of the stack should also be pushed onto the stack .
• hypothesis There are multiple elements in the original stack that are the same as the top element , When Original stack stay Pop up top element When , The auxiliary stack should also pop up this element , because There is only one such element in the auxiliary stack , It will not exist after deletion , This is not correct , Therefore, we should also put The same element as the top element of the monotone stack Join in Auxiliary stack in .

Time complexity ：

$O(1)$

Code ：（ Array simulation stack implementation ）

class MinStack {
    
public:
    /** initialize your data structure here. */
    int stk[110], mn[110];
    int tt1 = 0, tt2 = 0;
    
    MinStack() {
    

    }

    void push(int x) {
    
        stk[++tt1] = x;
        if (tt2 == 0) mn[++tt2] = x; // Insert the monotone stack directly when there are no elements 
        else {
    
            if (x <= mn[tt2]) mn[++tt2] = x; // When there are elements, judge and then insert the monotone stack 
            else return;
        }
    }

    void pop() {
    
        --tt1;
        if (stk[tt1 + 1] == mn[tt2]) --tt2;
    }

    int top() {
    
        return stk[tt1];
    }

    int getMin() {
    
        return mn[tt2];
    }
};

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