国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > [LeetCode] Min Stack

[LeetCode] Min Stack

来源:程序员人生   发布时间:2015-04-20 08:18:05 阅读次数:2209次

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.
解题思路:

主要是取得当前最小值的问题。我们可以用1个动态数组min存储当前最小值。若新压入的元素大于动态数组min最后1个元素,不做任何操作。否则(小于或等于)就压入min中。出栈的时候,若出栈元素等于min最后1个元素,则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⑴]>=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⑴]){ minSize--; } }else{ throw exception(); } } int top() { if(size>0){ return data[size⑴]; }else{ throw exception(); } } int getMin() { return min[minSize⑴]; } private: int size; int capcity; int* min; int minSize; int minCapcity; int* data; };

生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生