1.原题
链接:https://leetcode.com/problems/min-stack/
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
- push(x) -- Push element x onto stack.
- pop() -- Removes the element on top of the stack.
- top() -- Get the top element.
- getMin() -- Retrieve the minimum element in the stack.
Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.
2.题目大意
定义栈的数据结构,实现一个能够得到栈的最小元素的min函数。在该栈中,调用min、push及pop的时间复杂度都是O(1)
3.解题思路
为了能在O(1)时间内得到最小元素,需要有辅助的栈,保存当前的最小值,记为最小栈。这个辅助的栈,需在push(),pop()操作时更新,push时若当前最小栈为空或入栈的值<=最小栈栈顶的值,则将当前入栈的值压入最小栈;pop时,若出栈的值和最小栈栈顶的值相同,则最小栈也pop。
4.代码实现
public class MinStack {
ArrayList<Integer> stack=new ArrayList<>();
ArrayList<Integer> minStack=new ArrayList<>();
public void push(int x) {
stack.add(x);
if(minStack.isEmpty() || minStack.get(minStack.size()-1)>=x)
minStack.add(x);
}
public void pop() {
if(stack.isEmpty())
return;
int last=stack.remove(stack.size()-1);
if(!minStack.isEmpty() && minStack.get(minStack.size()-1)==last)
minStack.remove(minStack.size()-1);
}
public int top() {
if(stack.isEmpty())
return 0;
return stack.get(stack.size()-1);
}
public int getMin() {
if(minStack.isEmpty())
return 0;
return minStack.get(minStack.size()-1);
}
}