155. MinStack
題目:
希望你完成一個stack
可以pop push
同時可以知道裡面的最小值
思路：
因為要知道最小值
所以如果直接用一個stack紀錄值
喔個monotonic stack紀錄最小值的話
可能會出現一種情況
有重複數字出現
pop之後 數字沒了
min值也被pop掉的情況
所以就改用再多一個vector
記錄index對應的值
然後在stack裡面就用值來push pop
不過看解答後發現 其實
minstack也可以讓他==的時候也放進去
也會對就是了 因為就允許重複了
```cpp
class MinStack {
public:
vector<int> save;
vector<int> paper;
vector<int> minpaper;
MinStack() {
paper.clear();
save.clear();
minpaper.clear();
}
void push(int val)
{
save.push_back(val);
minpaper.push_back(save.size()-1);
while(minpaper.size()>1 && save[minpaper[minpaper.size()-1]] > save[mi
np
aper[minpaper.size()-2]])
{
minpaper.pop_back();
}
paper.push_back(save.size()-1);
}
void pop() {
if(minpaper.back() == paper.back())
{
minpaper.pop_back();
}
paper.pop_back();
}
int top()
{
return save[paper.back()];
}
int getMin()
{
return save[minpaper.back()];
}
};
```