155. 最小栈
题目描述:
设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。
push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
解题思路:
实现栈很容易,使用内置集合list就可实现,但是要实现检索到最小值,需要一个辅助栈来记录当前栈的最小值。
当元素入栈时,正常栈直接push。而记录最小元素的栈,需要判断。
若当前入栈元素小于最小元素栈的栈顶元素,则当前元素入栈最小栈。
若当前元素大于等于最小栈栈顶元素,则最小栈重新将栈顶元素入栈一遍。
图解:
代码实现:
public class MinStack {
//主栈
private List<Integer> data;
//最小值栈
private List<Integer> minStack;
public MinStack() {
data = new ArrayList<>();
minStack = new ArrayList<>();
}
public void push(int x) {
//若栈空,说明最小栈也为空,全部直接入栈
if (data.isEmpty()) {
data.add(x);
minStack.add(x);
}else {
//主栈直接入栈
data.add(x);
//最小值栈将当前入栈元素与最小值栈栈顶元素进行比较,然后入栈
minStack.add(x < minStack.get(minStack.size() - 1) ? x : minStack.get(minStack.size() - 1));
}
}
public void pop() {
data.remove(data.size() - 1);
minStack.remove(minStack.size() - 1);
}
public int top() {
return data.get(data.size() - 1);
}
//获取最小值,即返回最小值栈栈顶元素
public int getMin() {
return minStack.get(minStack.size() - 1);
}
public int getSize() {
return data.size();
}
}