返回信息流第一次做OJ，智商被压制了。原题目是这样的：
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.
刚好最近刚看primer中的vector，就用vector试了一下，代码如下：
#include<vector>
#include<iostream>
#include<cstdlib>
using std::vector;
class MinStack {
private:
vector<int> stack,minstack;
public:
void push(int x) {
if(stack.empty() || x<minstack.back())
{
minstack.push_back(x);
}
stack.push_back(x);
}
void pop() {
if(stack.empty())
return;
if(stack.back()==minstack.back())
minstack.pop_back();
stack.pop_back();
}
int top() {
return stack.back();
}
int getMin() {
return minstack.back();
}
};
void main()
{
MinStack s;
for(int i=0;i<10;i++)
{
s.push((i-5)*(i-5));
std::cout << "min_val = " << s.getMin() << "\ttop_val = " << s.top() << std::endl;
}
system("pause");
}
结果无情的被告知内存超过限制[ema1]
看人家的代码使用双端队列做的：
#include <iostream>
#include <deque>
using namespace std;
//因为需要在constant time当中获得最小值，将最小值单独存储
class MinStack {
public:
void push(int x) {
stack.push_front(x);
if (minStack.empty() || minStack.front() >= x)
{
minStack.push_front(x);
}
}
void pop() {
if(stack.empty())
{
return;
}
if(stack.front() == minStack.front())
{
minStack.pop_front();
}
stack.pop_front();
}
int top() {
if(stack.empty())
{
return 0;
}
return stack.front();
}
int getMin() {
if(minStack.empty())
{
return 0;
}
return minStack.front();
}
private:
deque<int> stack;
deque<int> minStack;
};
int main()
{
MinStack stack;
stack.push(512);
stack.push(1024);
stack.push(1024);
stack.push(512);
stack.pop();
stack.getMin();
stack.pop();
stack.getMin();
stack.pop();
stack.getMin();
}
Ctrl+C +V后就通过了。瞬间就崩塌了[ema36]。
那么问题来了，为什么vector不行deque就可以呢？
他们在内存开销上有什么区别吗？
新手，请轻拍[ema23]
这是一条镜像帖。来源：北邮人论坛 / cpp / #84797同步于 2014/12/19
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
[问题]leetcode的Min Stack的疑问
kizy008
2014/12/19镜像同步7 回复
订阅后，新回复会通过你的通知中心匿名送达。
7 条回复
个人猜测是这样的，vector容器一般只会自增，不会自减，可能会造成容器中有很多没有用到的空间，而且每次申请都是申请当前空间的2倍。deque是动态管理存储，用的是堆空间，把一段一段的空间虚拟的当做连续的线性空间，试着猜测一下，当数据量减少的时候，deque应该也会适当的释放内存。
然后我看了一下stack的声明：template <class T, class Container = deque<T> > class stack;默认也是用的deque容器。
坐等大神解释。
【 在 libenchao 的大作中提到: 】
: 个人猜测是这样的，vector容器一般只会自增，不会自减，可能会造成容器中有很多没有用到的空间，而且每次申请都是申请当前空间的2倍。deque是动态管理存储，用的是堆空间，把一段一段的空间虚拟的当做连续的线性空间，试着猜测一下，当数据量减少的时候，deque应该也会适当的释放内存。
: 然后我看了一下stack的声明：template <class T, class Container = deque<T> > class stack;默认也是用的deque容器。
: 坐等大神解释。
看来还有好多东西要学啊，受教了。真心点个赞！[ema4]
额，代码好像没粘全
【 在 buptxrc (若晨团 && 江南西道 && cstdlib.com) 的大作中提到: 】
: 且不说内存的事，你的push里面少了个 =
: [ema1][ema1]
通过『我邮2.0』发布