2015.1.23 12:13

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

　　push(x) -- Push element x onto stack.

　　pop() -- Removes the element on top of the stack.

　　top() -- Get the top element.

　　getMin() -- Retrieve the minimum element in the stack.

Solution:

　　This could almost be counted as a FAQ. You'll find a same question in "Cracking the Coding Interview". A min stack is maintained alongside the data stack, recording every minimal (so far) element. The min stack is updated whever a new minimal value is being pushed, or the current minimal value is being popped.

　　Total time complexity for each operation is strictly O(1). Extra space of O(n) is required to maintain the min stack.

Accepted code:

1 // 1AC, old 2 #include 
     
       3 using namespace std; 4  5 class MinStack { 6 public: 7     void push(int x) { 8         if (ms.empty() || ms.top() >= x) { 9             ms.push(x);10         }11         s.push(x);12     }13 14     void pop() {15         if (s.top() == ms.top()) {16             ms.pop();17         }18         s.pop();19     }20 21     int top() {22         return s.top();23     }24 25     int getMin() {26         return ms.top();27     }28 private:29     stack
      
        s, ms;30 };