题目描述
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。
分析
要在常数时间内获取最小值，必定空间换时间，把当前栈的最小值用另外一个数据结构存起来。
最好的解决方法就是辅助栈——和数据栈一样，只不过存的是当前栈的最小值。
同步辅助栈
辅助栈和数据栈大小一致：元素之间相互映射，数据栈元素对应的辅助栈元素是数据栈该元素到栈底的最小元素。
class LC_155 {
private Stack<Integer> stack;
private Stack<Integer> helper;
public LC_155() {
stack = new Stack<>();
helper = new Stack<>();
}
public void push(int x) {
stack.push(x);
if (helper.isEmpty())helper.push(x);
else helper.push(x>helper.peek()?helper.peek():x);
}
public void pop() {
helper.pop();
stack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return helper.peek();
}
}
不同步辅助栈
辅助栈和数据栈维持相同大小--空间开销
如何减少空间开销？？？
可以重减少辅助栈中重复值入手：
例：
插入1,2,3，辅助栈中存放的全部是1，造成了空间浪费：
现在考虑插入时，辅助栈只存放小于当前最小值的。
辅助栈的出栈怎么办？
举例：
1 1
2 0
1
0
3
只有当两个栈栈顶相同的时候辅助栈才出栈，数据栈3出栈时辅助栈0不出栈，0出栈时它才出栈
问题来了：数据栈1出栈时把辅助栈的1带出栈了，造成不匹配。
原因就是插入时的重复值问题，入栈时和最小值相同才行，才能在出栈时不被破坏。
于是改变原来的策略：当前元素<=最小值时辅助栈插入，只有大于时不插入。
上面的例子：
1 1
2 1
1 0
0
3
操作：
数据栈3出栈，辅助栈不出栈，最小值还是0
数据栈0出栈，辅助栈0也出栈，最小值是1
数据栈1出栈，辅助栈1出栈，最小值是1
数据栈2出栈，辅助栈1不出栈，最小值是1
数据栈1出栈，辅助栈1也出栈，两个栈皆空
可见算法是可以工作的。
减少了空间，必然由于各种判断增加时间
class MinStack{
private Stack<Integer> stack;
private Stack<Integer> helper;
public MinStack() {
stack = new Stack<>();
helper = new Stack<>();
}
public void push(int x) {
stack.push(x);
if (helper.isEmpty())helper.push(x);
else if(x<=helper.peek()){
helper.push(x);
}
}
public void pop() {
int tmp= stack.pop();
if (helper.peek()==tmp) helper.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return helper.peek();
}
}
不用辅助栈
上面的辅助栈不过是通过是数据栈元素的一个映射
- 同步的是一对一映射
- 不同步的是一对多映射
那不用辅助栈也行，直接定义类Ele<元素，最小值>，把Ele当做数据栈的元素不就好了！
更直接地，不要其他数据复合数据类型也行，题目中使用的是Integer数据类型，那我使用Long类型的栈Stack