【LeetCode】【算法】155. 最小栈

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();*/