1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class MinStack{
private:
stack<pair<int,int>> minStack_;
vector<int> data_;
private:
public:
MinStack(){
}
void push(int val){
data_.push_back(val);
sort(data_.begin(),data_.end(), [](int a,int b){
return a < b;
});
pair<int,int> result(val,data_.front());
minStack_.push(result);
}
void pop(){
int delData = minStack_.top().first;
minStack_.pop();
auto its = std::find(data_.begin(), data_.end(),delData);
if (its != data_.end()){
data_.erase(its);
}
}
int top(){
return minStack_.top().first;
}
int getMin(){
return minStack_.top().second;
}
};
|
早先做这道题的时候，采用的是双栈，想法简单，却也要在两个栈中来回移动，极其愚蠢。后面看别人的题解的时候看到利用 pair<int,int> 的应用，甚是美妙，可我还是走错了（data_ 的使用是画蛇添足）。直到再次看到另一个人的题解，我才明白我的思想究竟错误在哪里，也回忆起之前感叹美妙的原由，即采用 pair<int,int> 只需一个栈；加入元素就与 top 元素 进行 min 求值，就能保证当前 元素记录着对应 栈的最小元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class MinStack{
private:
stack<pair<int,int>> minStack_;
public:
MinStack(){
}
void push(int val){
pair<int,int> result;
if (minStack_.empty()){
result = pair<int,int>(val,min(val,val));
}else{
result = pair<int,int>(val,min(val,minStack_.top().second));
}
minStack_.push(result);
}
void pop(){
minStack_.pop();
}
int top(){
return minStack_.top().first;
}
int getMin(){
return minStack_.top().second;
}
};
|
