设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。
示例:
输入： ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]] 输出： [null,null,null,null,-3,null,0,-2] 解释： MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.
提示：
pop、top 和 getMin 操作总是在 非空栈 上调用。
Related Topics
栈
设计
思路1：暴力法class MinStack {
int[] stack = new int[10000];
int last = -1;
public MinStack() {
}
public void push(int val) {
stack[++last] = val;
}
//因为操作都是在非空栈进行
public void pop() {
last--;
}
public int top() {
return stack[last];
}
public int getMin() {
int min = stack[0];
for(int i = 1 ; i <= last;i++){
if(min >stack[i]){
min = stack[i];
}
}
return min;
}
}
解答成功:
执行耗时:53 ms,击败了7.10% 的Java用户
内存消耗:42.8 MB,击败了11.99% 的Java用户
思路2：使用辅助栈存储当前值和之前的最小值
class MinStack {
int[] stack = new int[10000];
int last = -1;
//存储栈中当前值之前的最小值
int[] tempStack = new int[10000];
public MinStack() {
}
//在入栈的时候给
public void push(int val) {
stack[++last] = val;
tempStack[last] = val;
if(last >0 && tempStack[last-1] < val){
tempStack[last] = tempStack[last-1];
}
}
//因为操作都是在非空栈进行
public void pop() {
last--;
}
public int top() {
return stack[last];
}
public int getMin() {
return tempStack[last];
}
}
解答成功:
执行耗时:4 ms,击败了98.32% 的Java用户
内存消耗:44.8 MB,击败了5.01% 的Java用户
思路3：常数级的额外空间思路
思路：栈中存储第i项值和前i-1项最小值的差值 dis = val - min
那么怎么恢复这个val呢？
如果 dis > 0,直接用栈中存储的值加上min
如果dis <= 0 那么这个val在push的时候会被更新成min，说明min就是val。
因为栈中存储的是差值，当min是-2147483648时，dis就会溢出，所以使用long型解决溢出问题。
class MinStack {
long[] stack = new long[10000];
int last = -1;
long dis = 0;
long min = 0;
//存储栈中当前值之前的最小值
//int[] tempStack = new int[10000];
public MinStack() {
}
public void push(int val) {
if(last == -1){
stack[++last] = (long) 0;
min = (long) val;
}else{
dis = (long) (val - min);
stack[++last] = dis;
//更新最小值
if(val < min){
min = (long) val;
}
}
}
//因为操作都是在非空栈进行
public void pop() {
dis = stack[last--];
//
if(dis < 0){
min = min - dis;
}
}
public int top() {
dis = stack[last];
if(stack[last] > 0){
return (int) (dis + min);
}else{
return (int) min;
}
}
public int getMin() {
return (int) min;
}
}
解答成功:
执行耗时:4 ms,击败了98.27% 的Java用户
内存消耗:44.5 MB,击败了5.05% 的Java用户
