[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;
  };