g********r
发帖数: 89 | 1 Leetcode给的solution，在pop的时候，只要栈顶元素=minStack栈顶元素，就把
minStack的栈顶元素pop掉。如果有duplicates的话，比如stack里面5, 3, 3，
minStack里面是5, 3，在pop第一个3的时候，不应该把minStack里面的3 pop掉吧。否
则Stack里面变成了5, 3, minStack里面是5, 答案是不是有问题？
---- Leetcode solution
public void pop() {
if (stack.pop().equals(minStack.peek())) minStack.pop();
}
-----my solution
void pop() {
if(stk.empty()) return;
int tmp=stk.top();
stk.pop();
if(stk.empty() || (tmp == min_stk.top() && stk.top() > min_stk.top()
))
{
min_stk.pop();
}
} |
h******o
发帖数: 6 | 2 3 也会被push进去两次 所以pop 3 没问题 |
g********r
发帖数: 89 | 3 i see. 仔细看了一下LeetCode solution，如果当前最小元素一直重复的话，会被重复
push到minStack里面。这样显然不好啊，没想到LeetCode没考虑到？
-----
public void push(int x) {
stack.push(x);
if (minStack.isEmpty() || x <= minStack.peek()) {
minStack.push(x);
}
} |
h**d
发帖数: 630 | 4 不这样 不就又出现你开始问的问题了 所以必须重复push min
★ 发自iPhone App: ChineseWeb 7.8
【在 g********r 的大作中提到】
: i see. 仔细看了一下LeetCode solution，如果当前最小元素一直重复的话，会被重复
: push到minStack里面。这样显然不好啊，没想到LeetCode没考虑到？
: -----
: public void push(int x) {
: stack.push(x);
: if (minStack.isEmpty() || x <= minStack.peek()) {
: minStack.push(x);
: }
: }
|
g********r
发帖数: 89 | 5 我的意思是说这很浪费啊，重复元素push一次就好了。
【在 h**d 的大作中提到】
: 不这样 不就又出现你开始问的问题了 所以必须重复push min
:
: ★ 发自iPhone App: ChineseWeb 7.8
|
n******r
发帖数: 147 | 6 那你pop一个元素的时候，你怎么判断要不要从minStack也pop？
【在 g********r 的大作中提到】
: 我的意思是说这很浪费啊，重复元素push一次就好了。
|
g********r
发帖数: 89 | 7 void pop() {
if(stk.empty()) return;
int tmp=stk.top();
stk.pop();
if(stk.empty() || (tmp == min_stk.top() && stk.top() > min_stk.top()
))
{
min_stk.pop();
}
}
【在 n******r 的大作中提到】
: 那你pop一个元素的时候，你怎么判断要不要从minStack也pop？
|
I**********s
发帖数: 441 | 8 可以保持一个counter, 数元素出现了多少次.
class MinStack {
stack s;
stack > smin;
public:
void push(int x) {
if (smin.empty()) {
smin.push(pair(x, 1));
}
else {
if (x < smin.top().first) { smin.push(pair(x, 1)); }
else { smin.top().second += 1; }
}
s.push(x);
}
void pop() {
s.pop();
if (smin.top().second == 1) { smin.pop(); }
else { smin.top().second -= 1; }
}
int top() {
return s.top();
}
int getMin() {
return smin.top().first;
}
};
【在 n******r 的大作中提到】
: 那你pop一个元素的时候，你怎么判断要不要从minStack也pop？
|
g********r
发帖数: 89 | 9 用不到counter，这个也浪费。
每次pop的时候，如果stack pop的元素和minStack栈顶想同，那么继续判断他下面的元
素是不是比minStack栈顶大，就知道他是不是第一个重复的元素了。
【在 I**********s 的大作中提到】
: 可以保持一个counter, 数元素出现了多少次.
: class MinStack {
: stack s;
: stack > smin;
: public:
: void push(int x) {
: if (smin.empty()) {
: smin.push(pair(x, 1));
: }
: else {
|
i**********e
发帖数: 1145 | 10 How about the following test case:
push(0),push(1),push(0),pop(),getMin()
Your solution should get Runtime Error now.
【在 g********r 的大作中提到】
: 用不到counter，这个也浪费。
: 每次pop的时候，如果stack pop的元素和minStack栈顶想同，那么继续判断他下面的元
: 素是不是比minStack栈顶大，就知道他是不是第一个重复的元素了。
|
s****z
发帖数: 18 | 11 我去...原作者出现了?
【在 i**********e 的大作中提到】
: How about the following test case:
: push(0),push(1),push(0),pop(),getMin()
: Your solution should get Runtime Error now.
|
g********r
发帖数: 89 | 12 谢谢，你说的是对的。重复元素似乎没办法节省开支了。。
不过你的test case也是才加上去的吧？^_^ hehe，一个小时前还是AC, now failed...
【在 i**********e 的大作中提到】
: How about the following test case:
: push(0),push(1),push(0),pop(),getMin()
: Your solution should get Runtime Error now.
|
x*****a
发帖数: 610 | 13 What if 重复的元素并不是他下面紧接着的第一个呢？
比如push(0),push(1),push(0)
之后你pop(0)的时候删不删minStack最顶上，也是唯一的那个0？
难不成得把整个stack检查一遍？
【在 g********r 的大作中提到】
: 用不到counter，这个也浪费。
: 每次pop的时候，如果stack pop的元素和minStack栈顶想同，那么继续判断他下面的元
: 素是不是比minStack栈顶大，就知道他是不是第一个重复的元素了。
|
