Redian新闻
>
[转让]/[交换]转让: 3off 15 coupon code
avatar
[转让]/[交换]转让: 3off 15 coupon code# PennySaver - 省钱一族
f*f
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();
}
};
avatar
m*j
2
不建议交易打印胖子;胖子是免费的,收费的是服务:
出售/交换物品的名称:
转让: 3off 15 coupon code
物品类别(coupon:mfc等;血糖仪等):
COUPON CODE
物品来源(报纸夹页,厂家邮寄等):
RITEAID
可接受的价格(必须明码标价,必填):
4个包子EACH
邮寄损失方式哪方承担(若需邮寄,必填):
付款方式说明:
本贴有效期(必填):
TILL GONE
联系方式(例: 站内):
站内
avatar
l*g
3
你的skm用的浪费啦!大数就不要push了。。。然后memory就够了
avatar
b*g
4
才发现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

avatar
f*f
5
多谢,确实问题多多....
avatar
z*m
6
主要是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();
}

}
avatar
g*9
7
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;
}
avatar
f*u
8
应该是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);
: }
: }

avatar
r*e
9
记得有不用额外的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

avatar
n*u
10

discussion里面有个自己加个node class上去不用stack的写法。

【在 r*****e 的大作中提到】
: 记得有不用额外的stack的解法啊,不过似乎leetcode不支持long long int
: 没法handle underflow的情况。比如,push(int_max), push(int_min)的
: 情况。
: 有人用不要额外的stack试过吗?

avatar
r*e
11
还是用stack正常啊
还是想看看不用额外的stack的
能过oj的解法

【在 n*********u 的大作中提到】
:
: discussion里面有个自己加个node class上去不用stack的写法。

avatar
b*g
12
不用额外的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试过吗?

avatar
r*e
13
就是当要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解法?愿闻其详

avatar
r*e
14
又想了想,用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

avatar
b*g
15
思路倒是很巧妙。不过用long long感觉memory更差啊,space直接变成2n。用2个stack
的话最差情况才是2n。而且操作还简单。

【在 r*****e 的大作中提到】
: 又想了想,用long long memory上
: 没比用额外的stack好。

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。