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

怼烎@ 2024-03-27 16:07 39阅读 0赞

> 这是一道 **中等难度** 的题。
> 
> 题目来自：[leetcode][]

### 题目 ###

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

**实现 MinStack 类:**

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

**提示：**

*   − 2 31 < = v a l < = 2 31 − 1 -2^\{31\} <= val <= 2^\{31\} - 1 −231<=val<=231−1
 *  `pop`、`top` 和 `getMin` 操作总是在 **非空栈** 上调用
 *  `push`, `pop`, `top`, and `getMin`最多被调用次 3 ∗ 1 0 4 3 \* 10^4 3∗104

### 解题思路 ###

这道题的重点是 `getMin()`用常数时间获取栈中的最小元素，其他几点是栈本身就支持了的功能。

**那么该如何获取栈中的最小值呢？** 无非就两种思路：

1.  元素入栈时就计算出对应的最小值，并将最小值和入栈元素以对应的关系关联存储。
2.  元素入栈时不做处理，获取最小值的时候实时计算。

本题题解采用第一种方式，入栈时计算，并将最小值和入栈元素以数组的形式一同入栈，数组中的第一个位置存原始入栈的数据，第二个位置存当前计算得出的最小值。

假如入栈元素为：`-1，1，2，-2`。

*  那么入栈时存储的数据依次为：
 *   *  \{-1, -1\}
     *  \{1, -1\}
     *  \{2, -1\}
     *  \{-2, -2\}
 *  删除栈顶元素：直接删除栈顶数组即可，原始数据和最小值被一同删除。
 *  获取栈顶元素：获取到栈顶数组的第一个位置存放的值。
 *  获取最小值：获取到栈顶数组的第二个位置存放的值。

![图片][a5d468902be0e1bef16871d133232c33.gif]

### 代码实现 ###

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];
        }
    }

[leetcode]: https://leetcode.cn/problems/min-stack/
[a5d468902be0e1bef16871d133232c33.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/1b6c1365cfa744b594652affd9ff1c44.png