LeetCode 155. 最小栈
题目描述
设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
思路
思路:一个栈,栈内元素存储一个数组实现,其中第一个元素是存储元素值,第二个元素是存储的栈中元素最小值
第一步:定义队列:Deque<int[]> deque;
第二步:MinStack()初始化:deque = new ArrayDeque();
第三步:void push(int val),压入栈时判断需要存储的数组的第二个元素大小:① 如果栈为空,则deque.push(new int[]{val, val}); ② 如果栈不为空,如果deqeue.peek()[1]>val,则deque.push(new int[]{val, val}); 否则deque.push(new int[]{val,deque.peek()[1]});
第四步:void pop(),deque.pop()即可
第五步:int top(),return deque.peek()[0]即可
第六步:int getMin(),return deque.peek()[1]即可
代码
class MinStack {Deque<int[]> deque;public MinStack() {deque = new ArrayDeque<>();}public void push(int val) {if (deque.isEmpty()) {deque.push(new int[]{val, val});} else {int[] peek = deque.peek();if (peek[1] < val) {deque.push(new int[]{val, peek[1]});} else {deque.push(new int[]{val, val});}}}public void pop() {deque.pop();}public int top() {return deque.peek()[0];}public int getMin() {return deque.peek()[1];}
}/*** Your MinStack object will be instantiated and called as such:* MinStack obj = new MinStack();* obj.push(val);* obj.pop();* int param_3 = obj.top();* int param_4 = obj.getMin();*/