【算法题解】15. 设计最小栈

小半 • 2023年12月28日上午11:54 • 数据结构 • 阅读 189

这是一道 中等难度 的题。

题目来自：https://leetcode.cn/problems/min-stack/

题目

设计一个支持 push ，pop ，top 操作，并能在 常数时间 内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

提示：

pop、top 和 getMin 操作总是在 非空栈 上调用
push, pop, top, and getMin最多被调用次

解题思路

这道题的重点是 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];
    }
}