怎么做王者荣耀网站,支付宝手机网站,哪个网站做视频有钱挣,wordpress安装资料夹关键词#xff1a;排序
题目#xff1a;最小栈
方法一#xff1a;在记录这个数的同时#xff0c;记录目前的最小值。看了提示才写出来的。
方法二#xff1a;辅助栈。辅助栈保持非严格递减。看了k神的答案。 方法一#xff1a;
一开始没想到怎么存最小#xff0c;看…关键词排序
题目最小栈
方法一在记录这个数的同时记录目前的最小值。看了提示才写出来的。
方法二辅助栈。辅助栈保持非严格递减。看了k神的答案。 方法一
一开始没想到怎么存最小看了评论的提示才想到的。
思路
关键一个栈的一个元素存两样大小这个数本身包括这个数在内目前栈的最小值。
存数的同时存截至到这个数为止的最小数。
注意min的比较是和栈的前一个min比不是和全局的min比。
min(xstack.back()[1])?x:stack.back()[1];
如果全局的min是1可是1已经被pop了但是这个min的记录还会是1就会出错。
复杂度计算
时间复杂度O(n)
空间复杂度O(n)
代码
class MinStack {
public:/** initialize your data structure here. */MinStack() {}void push(int x) {if(stack.empty()) minx;elsemin(xstack.back()[1])?x:stack.back()[1];stack.push_back({x,min});}void pop() {stack.pop_back();}int top() {return stack.back()[0];}int getMin() {return stack.back()[1];}
private:vectorvectorint stack;int minINT_MAX;
};/*** 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();*/
方法二
看了k神。用了两个栈A栈正常存数B栈存最小值B栈要保持非严格递减。
思路
入栈的时候还需要维护辅助栈。为什么要维护非严格降序的辅助栈
1、如果
B.top() x
则要把x存进B里面保持非严格降序这个时候x就是B里面最小的。
2、如果
B.top() x 则不用存x因为前面已经有B.top()小于x了x无论怎么样都不可能是最小值。
出栈的时候如果B.top()等于要A出栈的那个数那么B也要跟着出栈。理由当然是因为那个数跑了所以B当然要一起删掉。
非严格降序 复杂度计算
时间复杂度O(n)
空间复杂度O(n)
代码
class MinStack {
public:/** initialize your data structure here. */MinStack() {}void push(int x) {A.push(x);if(B.empty()||xB.top())B.push(x);}void pop() {if(A.top()B.top())B.pop();A.pop();}int top() {return A.top();}int getMin() {return B.top();}
private:stackint A;stackint B;
};/*** 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();*/
