这真的不用什么单调栈啊!(最易懂解法)
题目描述
blablabla
样例
blablabla
维护:
两个 stack,
stack[i][0] : 表示 i 数。
stack[i][1] : 表示 0-i 最小值
push 操作
void push(int x) {
v->push(x);
m->push(min(getMin(), x)); //[0,i]最小值 = min([0,i-1]最小值, i);
}
class MinStack {
stack<int>* v;
stack<int>* m;
public:
/** initialize your data structure here. */
MinStack() {
v = new stack<int>; //初始化
m = new stack<int>;
}
void push(int x) {
v->push(x);
m->push(min(getMin(), x)); //[0,i]最小值 = min([0,i-1]最小值, i);
}
void pop() {
v->pop();
m->pop();
}
int top() {
return v->top(); //返回栈顶,即整个最小值
}
int getMin() {
if (m->empty()) return 0x3f3f3f3f; //防止神奇 SF
return m->top();
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
1
粉兔%%%