这是一道 中等难度 的题。
题目来自:leetcode
题目
设计一个支持 push
,pop
,top
操作,并能在 常数时间 内检索到最小元素的栈。
实现 MinStack 类:
MinStack()
初始化堆栈对象。void push(int val)
将元素val
推入堆栈。void pop()
删除堆栈顶部的元素。int top()
获取堆栈顶部的元素。int getMin()
获取堆栈中的最小元素。
提示:
- −231<=val<=231−1-2^{31} <= val <= 2^{31} - 1−231<=val<=231−1
pop
、top
和getMin
操作总是在 非空栈 上调用push
,pop
,top
, andgetMin
最多被调用次3∗1043 * 10^43∗104
解题思路
这道题的重点是 getMin()
用常数时间获取栈中的最小元素,其他几点是栈本身就支持了的功能。
那么该如何获取栈中的最小值呢? 无非就两种思路:
- 元素入栈时就计算出对应的最小值,并将最小值和入栈元素以对应的关系关联存储。
- 元素入栈时不做处理,获取最小值的时候实时计算。
本题题解采用第一种方式,入栈时计算,并将最小值和入栈元素以数组的形式一同入栈,数组中的第一个位置存原始入栈的数据,第二个位置存当前计算得出的最小值。
假如入栈元素为:-1,1,2,-2
。
- 那么入栈时存储的数据依次为:
-
- {-1, -1}
- {1, -1}
- {2, -1}
- {-2, -2}
- 删除栈顶元素:直接删除栈顶数组即可,原始数据和最小值被一同删除。
- 获取栈顶元素:获取到栈顶数组的第一个位置存放的值。
- 获取最小值:获取到栈顶数组的第二个位置存放的值。
代码实现
class MinStack {private Deque<int[]> stack;public MinStack() {stack = new LinkedList<>();}public void push(int val) {int min = val;if(!stack.isEmpty()){int[] topArr = stack.peek();int preMin = topArr[1];if(preMin < min){min = preMin;}}stack.push(new int[]{val, min});}public void pop() {stack.pop();}public int top() {int[] topArr = stack.peek();return topArr[0];}public int getMin() {int[] topArr = stack.peek();return topArr[1];}
}