当前位置：首页 > article >正文

Leetcode 最小栈

article 2024/10/22 9:44:15

在这里插入图片描述

算法思想：

使用两个栈：
- stack 栈：用于正常的栈操作（存储所有压入的元素）。
- minStack 栈：专门用来存储每次压入元素时的当前最小值。
push 操作：
- 每当压入一个新元素时，首先将其压入 stack 栈。
- 同时，检查 minStack 栈顶元素是否比当前压入的元素大或相等，如果是，则将这个元素也压入 minStack，表示当前栈的最小值发生变化。
- 这样，无论何时压入一个新元素，minStack 始终保持栈的最小元素在栈顶。
pop 操作：
- 当从 stack 栈弹出元素时，检查这个弹出的元素是否与 minStack 栈顶元素相等。如果相等，则表明当前最小值被弹出，需要同步从 minStack 中弹出。
- 如果不同，则只从 stack 弹出即可。
top 操作：
- 直接返回 stack 栈的栈顶元素，即当前栈的顶部元素。
getMin 操作：
- 直接返回 minStack 栈顶的元素，这个栈顶元素就是当前 stack 中的最小值，因为我们保证了 minStack 始终存储着每次操作后的最小值。

时间复杂度分析：

由于每次 push、pop、top 和 getMin 操作都只涉及常数次的栈操作，所有操作的时间复杂度均为 O(1)。

通过这个算法，我们实现了在常数时间内（O(1)）进行压栈、出栈、查询栈顶元素和查询最小元素的功能，非常高效。

class MinStack {
    //成员变量
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() { //构造函数
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
        //判空条件必须先放在前面 
        // 必须是小于等于
        if(minStack.isEmpty() || val <= minStack.peek()) { 
            minStack.push(val);
        }
    }
    
    public void pop() {
        //为什么用equals()而不是==?
        // == 比较的是引用（内存地址）, equals() 比较的是值
        if(stack.peek().equals(minStack.peek())) {
            minStack.pop();
        }
        stack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

注意点

为什么这行代码的判断条件中，如果使用小于而不是小于等于也会出错？

if (minStack.isEmpty() || val <= minStack.peek())

在 MinStack 这个实现中，使用 小于等于（<=） 而不是 小于（<） 的原因与维护栈中最小值的正确性有关。下面我们详细解释为什么使用 < 会导致错误，以及为什么必须使用 <=。

问题分析：

首先，来看这段代码：

if (minStack.isEmpty() || val <= minStack.peek()) {
    minStack.push(val);
}

1. 使用小于（<）可能导致的错误：

逻辑问题：如果你使用的是 <，表示只有当当前要压入的值严格小于 minStack 栈顶元素时，才会将该值压入 minStack。这意味着相同的最小值不会被再次压入 minStack。
错误结果：如果栈中存在多个相同的最小值，例如连续压入多个值 3，当其中一个 3 被弹出时，你的 minStack 不会弹出这个 3，因为在栈顶只有一个 3，但实际上栈中还剩下多个 3。这样一来，minStack 不再能正确跟踪最小值。

举个例子：
- 假设你压入了三个元素：[3, 3, 3]，如果使用 <，minStack 中只会有一个 3，因为只有第一个 3 会被压入，后面的两个相等的 3 不会进入 minStack。
- 然后你执行三次 pop()：
  1. 第一次弹出栈顶 3，minStack 弹出 3。
  2. 第二次弹出栈顶 3，但是此时 minStack 已经为空（因为只存了一个 3），导致获取最小值时出错。

2. 为什么要使用小于等于（<=）：

逻辑保证：使用 <= 可以保证每次压入的值如果等于 minStack 栈顶元素，也会被压入 minStack，这样可以确保 minStack 里存储了所有最小值的拷贝。当多个最小值存在时，minStack 里会有多个相同的最小值。
正确性保证：这样做的好处是，当你从主栈 stack 弹出最小值时，minStack 中也会同步弹出该最小值，确保栈中仍然能正确返回当前的最小值。

示例说明：

假设你要压入 [3, 3, 2, 1, 1] 这些值。

当你使用 <= 时：
- minStack 会压入：[3, 3, 2, 1, 1]，这样你无论弹出多少个最小值，minStack 都能同步更新，始终保持栈中的最小值正确。
如果你使用 <：
- minStack 只会压入：[3, 2, 1]，当你弹出两个 1 时，minStack 只会弹出一个 1，导致 getMin() 在弹出第二个 1 后出错。