思路:
1.辅助栈
stack<int> dataStack, minStack;void push(int value) {if(minStack.empty() || value < minStack.top())minStack.push(value);dataStack.push(value);}void pop() {if(dataStack.empty())return;if(dataStack.top() == minStack.top())minStack.pop();dataStack.pop();}int top() {return dataStack.top();}int min() {return minStack.top();}
2.无辅助栈
stack<int> s;
int minVal, topVal;
void push(int value) {
if(s.empty())minVal = value;
s.push(value - minVal);//记录与之前最小值的差值
if(value < minVal)minVal = value;//更新最小值
topVal = value;
}
void pop() {
if(!s.empty()){
if(s.top() < 0){
minVal -= s.top();
}
s.pop();
if(!s.empty()){
topVal = minVal + (s.top() > 0 ? s.top() : 0);//如果小于等于0,说明它也是最小值
}
}
}
int top() {
if(!s.empty())
return topVal;
}
int min() {
if(!s.empty())
return minVal;
}
1.INT_MAX 2147483647
INT_MIN -2147483648
2.消除冗余值
每次存进value与最小值的差值
(1)大于0:比最小值大多少
(2)等于0:和最小值相等
(3)小于0:和之前最小值的差值,是新的最小值
出栈的时候,如果top小于0,要还原之前最小值
3.空栈调用top(),会报错
