155.最小栈

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

实现 MinStack 类:

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

思路

给你一个数组 nums，如何计算每个前缀的最小值？

定义 preMin[i] 表示 nums[0] 到 nums[i] 的最小值。

这可以从左到右计算：

preMin[0]=nums[0]。 preMin[1]=min(nums[0],nums[1])。 preMin[2]=min(nums[0],nums[1],nums[2])=min(preMin[1],nums[2])。 preMin[3]=min(nums[0],nums[1],nums[2],nums[3])=min(preMin[2],nums[3])。
……
一般地，我们有

preMin[i]=min(preMin[i−1],nums[i])

简单来说就是用额外的空间保存前缀的最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
package com.wereash.scut_hot100;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author: WereAsh
 * @Date:2026-01-25 20:36
 **/
public class Solution155 {

    public static void main(String[] args) {
        MinStack stack=new MinStack();
        stack.push(-2);
        stack.push(0);
        stack.push(-3);
        System.out.println(stack.top());
        stack.pop();
        System.out.println(stack.getMin());
    }
}
class MinStack{
    private Deque<int[]> stack;
    public MinStack() {
        stack=new LinkedList<>();
        stack.push(new int[]{0,Integer.MAX_VALUE});
    }

    public void push(int val) {
        stack.push(new int[]{val,Math.min(val,stack.peek()[1])}); //更新前缀最小值
    }

    public void pop() {
        stack.pop();
    }

    public int top() {
        return stack.peek()[0];
    }

    public int getMin() {
        return stack.peek()[1];//返回前缀最小值
    }
}