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