[LeetCode] Min Stack Min Stack

[LeetCode] Min Stack Min Stack

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. 解題思路：

  主要是獲得當前最小值的問題。我們可以用一個動態數組min存儲當前最小值。若新壓入的元素大於動態數組min最後一個元素，不做任何操作。否則（小於或等於）就壓入min中。出棧的時候，若出棧元素等於min最後一個元素，則min數組出棧。這樣便實現了常量時間找到棧中的最小值了。下面是代碼：

   

  class MinStack {
  public:
      MinStack(){
          capcity=2;
          data = new int[capcity];
          size=0;
          
          minCapcity=2;
          min = new int[minCapcity];
          minSize = 0;
      }
      ~MinStack(){
          delete[] data;
          delete[] min;
      }
      void push(int x) {
          if(size>=capcity){
              int* p=data;
              capcity = 2*capcity;
              data=new int[capcity];
              std::memcpy(data, p, sizeof(int)*size);
              delete[] p;
          }
          data[size++]=x;
          
          if(minSize==0){
              min[minSize++]=x;
          }else if(min[minSize-1]>=x){
              if(minSize>=minCapcity){
                  int* p=min;
                  minCapcity = 2*minCapcity;
                  min = new int[minCapcity];
                  std::memcpy(min, p, sizeof(int)*minSize);
                  delete[] p;
              }
              min[minSize++]=x;
          }
      }
  
      void pop() {
          if(size>0){
              size--;
              if(data[size]==min[minSize-1]){
                  minSize--;
              }
          }else{
              throw exception();
          }
      }
  
      int top() {
          if(size>0){
              return data[size-1];
          }else{
              throw exception();
          }
      }
  
      int getMin() {
          return min[minSize-1];
      }
  private:
      int size;
      int capcity;
      int* min;
      int minSize;
      int minCapcity;
      int* data;
  };