f********f
发帖数: 290 | 1 debug一下,也没什么问题阿
class MinStack {
stack sk;
stack skm;//min stack
public:
void push(int x) {
sk.push(x);
if(skm.empty() || skm.top()>x)
skm.push(x);
else
skm.push(skm.top());
}
void pop() {
sk.pop();
skm.pop();
}
int top() {
return sk.top();
}
int getMin() {
return skm.top();
}
}; |
l********g
发帖数: 372 | 2 你的skm用的浪费啦！大数就不要push了。。。然后memory就够了 |
b******g
发帖数: 3616 | 3 才发现LC又出新题了。不过这题也是cc150的原题啊。。。。
我理解你的算法应该是当栈每压入一个新的x时，你记录当前的min（要么是x要么是skm
.top())然后同时压入skm。但这么做的问题是，你浪费了很多空间在skm上。假如依次
压入1-1000，那么你就需要存储2000个int。而实际上这种情况下在skm里存一个1就行
了。所以一个改进就是：
对于push时：只有当x<=skm.top()，才压入x进skm
相应对于pop时：只有当sk.top()==skm.top()时，才pop skm。
刚写了一个过了LC
class MinStack {
stack s;
stack trackMin;
public:
void push(int x) {
s.push(x);
if(trackMin.empty() || x<=trackMin.top())
trackMin.push(x);
}
void pop() {
if(s.empty()) return;
if(s.top()==trackMin.top()) trackMin.pop();
s.pop();
}
int top() {
// 这里还需要判断当栈为空时应该如何操作，比如throw exception
return s.top();
}
int getMin() {
// 这里还需要判断当栈为空时应该如何操作，比如throw exception
return trackMin.top();
}
};
【在 f********f 的大作中提到】
: debug一下,也没什么问题阿
: class MinStack {
: stack sk;
: stack skm;//min stack
: public:
: void push(int x) {
: sk.push(x);
: if(skm.empty() || skm.top()>x)
: skm.push(x);
: else
|
f********f
发帖数: 290 | |
z***m
发帖数: 1602 | 5 主要是auxilary stack 太浪费， 只有当进来的数小于等于getMin(), 才push进。
void push(int x) {
if (st_aux.empty()) st_aux.push(x);
else {
if (x <= getMin()) {
//We only push to the min stack when the value being pushed onto
the main stack
//is less than or equal to the current min value
st_aux.push(x);
}
}
st.push(x);
}
相应的，pop的时候，只有当要出去的数等于getMin时才pop auxilary stack
void pop() {
if (!st_aux.empty() && st.top() == getMin()) {
st_aux.pop();
}
if (!st.empty()) {
st.pop();
}
} |
g****9
发帖数: 163 | 6 My code also complains memory limit exceed. Any suggestions why?
LinkedList stack = new LinkedList();
LinkedList ministack = new LinkedList();
public void push(int x) {
stack.add(x);
if (ministack.isEmpty() || ministack.getLast() >= x) {
ministack.add(x);
}
}
public void pop() {
if (stack.isEmpty()) {
return;
}
int ele = stack.removeLast();
if (!ministack.isEmpty() && ministack.getLast() == ele) {
ministack.removeLast();
}
}
public int top() {
if (!stack.isEmpty())
return stack.getLast();
return 0;
}
public int getMin() {
if (!ministack.isEmpty())
return ministack.getLast();
return 0;
} |
f*****u
发帖数: 308 | 7 应该是Java的LinkedList占的空间大了点，你改成Java自带的Stack就能过OJ了。
【在 g****9 的大作中提到】
: My code also complains memory limit exceed. Any suggestions why?
: LinkedList stack = new LinkedList();
: LinkedList ministack = new LinkedList();
:
: public void push(int x) {
: stack.add(x);
: if (ministack.isEmpty() || ministack.getLast() >= x) {
: ministack.add(x);
: }
: }
|
r*****e
发帖数: 792 | 8 记得有不用额外的stack的解法啊，不过似乎leetcode不支持long long int
没法handle underflow的情况。比如，push(int_max), push(int_min)的
情况。
有人用不要额外的stack试过吗？
【在 f********f 的大作中提到】
: debug一下,也没什么问题阿
: class MinStack {
: stack sk;
: stack skm;//min stack
: public:
: void push(int x) {
: sk.push(x);
: if(skm.empty() || skm.top()>x)
: skm.push(x);
: else
|
n*********u
发帖数: 1030 | 9
discussion里面有个自己加个node class上去不用stack的写法。
【在 r*****e 的大作中提到】
: 记得有不用额外的stack的解法啊，不过似乎leetcode不支持long long int
: 没法handle underflow的情况。比如，push(int_max), push(int_min)的
: 情况。
: 有人用不要额外的stack试过吗？
|
r*****e
发帖数: 792 | 10 还是用stack正常啊
还是想看看不用额外的stack的
能过oj的解法
【在 n*********u 的大作中提到】
:
: discussion里面有个自己加个node class上去不用stack的写法。
|
b******g
发帖数: 3616 | 11 不用额外的stack，应该也得用其他形式的额外空间吧。
比如用stack>，然后这个pair.first记录压入的数据，pair.second记
录压入时的min。但这样和两个stack其实也是一样的意思，而且占用空间更大。
存在constant extra space的单stack解法？愿闻其详
【在 r*****e 的大作中提到】
: 记得有不用额外的stack的解法啊，不过似乎leetcode不支持long long int
: 没法handle underflow的情况。比如，push(int_max), push(int_min)的
: 情况。
: 有人用不要额外的stack试过吗？
|
r*****e
发帖数: 792 | 12 就是当要push的value val小于当前的min时，push 2*val－min
这个值是小于val的，然后min更新为val。
当pop的时候，如果top的值小于min的话，就说明要把min pop出去了，
要更新min的值为 2＊min－top。相应的top函数也要做这样的转换。
不过这个算法做减法时会underflow，如果数据为int的话，但是用
long long oj memory exceeded limit
【在 b******g 的大作中提到】
: 不用额外的stack，应该也得用其他形式的额外空间吧。
: 比如用stack>，然后这个pair.first记录压入的数据，pair.second记
: 录压入时的min。但这样和两个stack其实也是一样的意思，而且占用空间更大。
: 存在constant extra space的单stack解法？愿闻其详
|
r*****e
发帖数: 792 | 13 又想了想，用long long memory上
没比用额外的stack好。
【在 r*****e 的大作中提到】
: 就是当要push的value val小于当前的min时，push 2*val－min
: 这个值是小于val的，然后min更新为val。
: 当pop的时候，如果top的值小于min的话，就说明要把min pop出去了，
: 要更新min的值为 2＊min－top。相应的top函数也要做这样的转换。
: 不过这个算法做减法时会underflow，如果数据为int的话，但是用
: long long oj memory exceeded limit
|
b******g
发帖数: 3616 | 14 思路倒是很巧妙。不过用long long感觉memory更差啊，space直接变成2n。用2个stack
的话最差情况才是2n。而且操作还简单。
【在 r*****e 的大作中提到】
: 又想了想，用long long memory上
: 没比用额外的stack好。
|
