每日一題--最小棧

1.線性時間尋找

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() 
    {
        
    }
    
    void push(int x)
     {
        size[cur]=x;
        cur++;
    }
    
    void pop() 
    {
         min=INT32_MAX;
        cur--;
    }
    
    int top()
     {
        return size[cur-1];
    }
    
    int getMin()
     {
        for(int i=0;i<cur;i++)
        {
            if(size[i]<min)
                min=size[i];
        }
        return min;
    }
private:
    int size[10000];
    int cur=0;
    int min=INT32_MAX;
};
           

2.O(1)的時間尋找

#include<iostream>
#include<stack>
using namespace std;
class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> Minstack;
    stack<int> mint;
    MinStack() 
    {
        mint.push(INT32_MAX);
    }
    
    void push(int x)
     {
        Minstack.push(x);
        mint.push(min(mint.top(),x));
    }
    
    void pop() 
    {
         Minstack.pop();
         mint.pop();
    }
    
    int top()
     {
       return Minstack.top();
    }
    
    int getMin()
     {
        return mint.top();
    }

};