LeetCode Min Stack

LeetCode Min Stack

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.
  Show Tags Have you met this question in a real interview? Yes No

  Discuss

  題意：寫一個新的棧：支持入棧，出棧，得到棧頂，和得到此時棧最小的那個數

  思路：前三個操作都可以用一個棧來實現，求最小的話就需要一個新的單調棧來維護了，這個新的單調棧需要注意的地方是：當原始的棧pop掉一個數的時候可能會影響到這個單調棧，只要判斷此時pop掉的話，是不是單調棧的棧頂就能解決了，因為這個單調棧是原始棧的子集

  
  

  class MinStack {
  public:
      void push(int x) {
          st.push(x);
          if (stm.empty() || stm.top() >= x) stm.push(x);
      }
  
      void pop() {
          int top = st.top();
          st.pop();
          if (top == stm.top()) stm.pop();
      }
  
      int top() {
          return st.top();
      }
  
      int getMin() {
          return stm.top();
      }
      
  private:
          stack st;
          stack stm;
  };