Daily practice (18): stack containing min function

---

title: Practice every day （18）： contain min Function of the stack

categories:[ The finger of the sword offer]

tags:[ Practice every day ]

date: 2022/02/14

---

Practice every day （18）： contain min Function of the stack

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 ：

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

source ： Power button （LeetCode）

link ：https://leetcode-cn.com/probl...

Method ： Stack

A stack is used to store all elements , Another stack is used to store the constantly updated minimum

pop If two stacks are detected top equal , That is, stack at the same time

min That is, return the smallest stack top

class MinStack {
public:
    /** initialize your data structure here. */
       stack<int>a,b; //b The stack is used to store the minimum value that is constantly updated 
    MinStack() {
    }
    
    void push(int x) {
        a.push(x);
        if (b.empty() || x <= b.top()) {
            b.push(x);
        }
    }
   
    void pop() {
        if (a.top() == b.top()) {
            b.pop();
        }
        a.pop();
    }
    
    int top() {
        return a.top();
    }
    
    int min() {
        return b.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->min();
 */