My C++ sulotion using STL<list> with 78ms


  • 0
    Y

    I don't think it's the fastest, but it is easy to read.
    I think that if we used the list defined by ourselves rather than the STL<list>, it would be faster.

    class MinStack {
        private:
        	list<int> s;
        	int min;
        
        
        public:
        
        	MinStack()
        	{
        		min=INT_MAX;
        	}
        
            void push(int x) {
        		if(x<min) min=x;
                s.push_back(x);
        		
            }
        
            void pop() {
        		if(s.back()==min)
        		{
        			s.pop_back();
        			min=INT_MAX;
        			list<int>::iterator it=s.begin();
        			while(it!=s.end())
        			{
        				if(*it<min) min=*it;
        				it++;
        			}
        		}else
        			s.pop_back();
            }
        
            int top() {
                return s.back();
            }
        
            int getMin() {
                return min;
            }
        };

  • 0
    P

    pop() is not O(1) since it has to traverse the list looking for the new minimum.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.