[LeetCode] Min Stack

Min Stack

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

解题思路：

主要是获得当前最小值的问题。我们可以用一个动态数组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;};

泪，一种痛苦的雨滴，不知从什么时候开始已在我的世界下个不停。