最小栈

LeetCode 155 最小栈

题目：

设计一个支持 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 操作总是在 非空栈 上调用。

来源：力扣（LeetCode） 链接：link

代码 JAVA

import java.util.*; public class MinStack { public static void main(String[] args) { // TODO 自动生成的方法存根 } private Stack<Integer> data; private Stack<Integer> helper; public MinStack() { data = new Stack<>(); helper = new Stack<>(); } public void push(int x) { data.add(x); if(helper.isEmpty() || helper.peek() >= x) { helper.add(x); }else { helper.add(helper.peek()); } } public void pop() { if(!data.isEmpty()) { helper.pop(); data.pop(); } } public int top() { if(!data.isEmpty()) { return data.peek(); } throw new RuntimeException("栈中元素为空，此操作非法"); } public int getMin() { if(!helper.isEmpty()) { return helper.peek(); } throw new RuntimeException("栈中元素为空，此操作非法"); } }

注意：

stack1.peek() 返回栈顶元素，但不在堆栈中删除它。 Stack2.pop() 返回栈顶元素，并在进程中删除它。 总结一下： 当我们只需要取出栈顶的元素进行处理（或者说我们需要先对栈顶的数据进行处理例如比较）然后根据处理的结果进行决定是否要pop()，这种情况下，我们可以先使用peek()方法，取出栈顶的值。 补充总结一下栈中的其他常用的方法： empty( )——如果堆栈是空的，则返回true，当堆栈包含元素时，返回false；