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()];
}
};
```