免费分销系统_web前端开发工程师在社会的工资_临沂seo公司_新媒体营销六种方式

算法思想：

1. 使用两个栈：

   • stack 栈：用于正常的栈操作（存储所有压入的元素）。
   • minStack 栈：专门用来存储每次压入元素时的当前最小值。

2. push 操作：

   • 每当压入一个新元素时，首先将其压入 stack 栈。
   • 同时，检查 minStack 栈顶元素是否比当前压入的元素大或相等，如果是，则将这个元素也压入 minStack，表示当前栈的最小值发生变化。
   • 这样，无论何时压入一个新元素，minStack 始终保持栈的最小元素在栈顶。

3. pop 操作：

   • 当从 stack 栈弹出元素时，检查这个弹出的元素是否与 minStack 栈顶元素相等。如果相等，则表明当前最小值被弹出，需要同步从 minStack 中弹出。
   • 如果不同，则只从 stack 弹出即可。

4. top 操作：

   • 直接返回 stack 栈的栈顶元素，即当前栈的顶部元素。

5. 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 后出错。

总结：

• 使用 <= 可以保证当你压入多个相同的最小值时，minStack 会存储每一个相等的最小值，这样在弹出元素时能够正确同步更新最小值。
• 如果使用 <，那么相等的最小值不会被重复压入，这会导致在弹出多个相同的最小值时，minStack 无法正确更新，进而导致错误的最小值返回。

因此，为了保持最小栈逻辑的正确性，必须使用 <= 来确保每个相等的最小值都被记录下来。