Force deduction 155 questions, minimum stack

Power button 155 topic , Smallest stack

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 :

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 .

I/o sample

 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.

Solution 1 ： Regardless of time complexity , Use vector

class MinStack{
    
public:
    MinStack()
    {
    
        nums={
    };
    }

    void push(int val)
    {
    
        nums.push_back(val);
    }

    void pop()
    {
    
        nums.pop_back();
    }
    
    int top()
    {
    
        // cout<<*(nums.end()-1)<<endl;
        return *(nums.end()-1);
    }

    int getMin()
    {
    
        int length=nums.size();
        int minValue=nums[0];
        for(int i=0;i<length;i++)
        {
    
            minValue=min(minValue,nums[i]);
        }
        // cout<<minValue<<endl;
        return minValue;
    }
private:
    vector<int>nums;
};

Solution 2 ： Use the auxiliary stack

// Use the auxiliary stack , One as the data stack , One as the smallest stack 
class  MinStack2{
    
private:
    stack<int>dataStk;
    stack<int>minStk;
public:
    MinStack2()
    {
    
        // The minimum stack initializes a maximum value into the stack first 
        minStk.push(INT_MAX);

    }

    void push(int val)
    {
    
        dataStk.push(val);
        minStk.push(min(minStk.top(),val));
    }

    void pop()
    {
    
        dataStk.pop();
        minStk.pop();
    }

    int top()
    {
    
        // cout<<dataStk.top()<<endl;
        return dataStk.top();
    }

    int getMin()
    {
    
    // cout<<minStk.top()<<endl;
        return minStk.top();
    }
};

Solution 3 , No auxiliary stack , Do not use extra space , Stack save difference

// Not applicable for additional space 
class MinStack3
{
    
private:
    int minValue=NULL;
    stack<long>dataStk;
public:
    MinStack3()
    {
    

    }

    void push(int val)
    {
    
        if(dataStk.empty())
        {
    
            dataStk.push(0L);
            minValue=val;
        }

        else
        {
    
            // What is stored in the data stack is the difference between the number and the minimum 
            dataStk.push(long(val)-minValue);
            minValue=min(val,minValue);

        }
    }

// If interpolation diff Greater than or equal to 0, It indicates that the value to be published is greater than or equal to the current min, Then the value to be out of the stack is not updated when entering the stack min, return min+diff
//  If interpolation diff Less than 0, It indicates that the current value to be published is min( Because when entering the stack, we choose min And the minimum value of the stack element ), meanwhile , adopt min-diff Before calculating min
// It should be noted that diff May exceed int Range , Be similar to  Integer.MAX_VALUE - 1  such , therefore diff Use Long save 
    void pop()
    {
    
        long diff=dataStk.top();
        dataStk.pop();
        if(diff>=0)
        {
    

        }
        else
        {
    
            int res=minValue;
            minValue=minValue-diff;
        }
    }


    int top()
    {
    
        long diff=dataStk.top();
        if(diff>=0)
        {
    
            // cout<<minValue+diff<<endl;
            return minValue+diff;
        }
        else{
    
            // cout<<minValue<<endl;
            return minValue;
        }

    }

    int getMin()
    {
    
        // cout<<minValue<<endl;
        return minValue;
    }

};