LeetCode: 155 Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) — Pushes element x onto the stack.
• pop() — Removes the element on the top of the stack.
• top() — Gets the top element.
• getMin() — Retrieves the minimum element in the stack.

Example:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   // return -3
minStack.pop();
minStack.top();      // return 0
minStack.getMin();   // return -2

问题

设计一个支持 push、pop、top 和在常数时间内检索最小元素的栈。

• push(x) — 将元素 x 推入栈中。
• pop() — 移除栈顶的元素。
• top() — 获取栈顶元素。
• getMin() — 检索栈中的最小元素。

解决方案

双栈法

Approach 1: Two Stacks / 双栈法

This approach uses two stacks: one to store all the elements (regular stack) and another to store the minimum values (min stack). The min stack is updated only when a new minimum is encountered.

这种方法使用两个栈：一个存储所有元素（普通栈），另一个存储最小值（最小栈）。当遇到新的最小值时，才更新最小栈。

Implementation / 实现

Python

class MinStack:

    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)

    def pop(self) -> None:
        if self.stack[-1] == self.min_stack[-1]:
            self.min_stack.pop()
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

Explanation / 解释

1. Initialize the Stacks / 初始化栈

   self.stack = []
   self.min_stack = []

   • English: We initialize two stacks: stack for storing all elements, and min_stack for keeping track of the minimum values.
   • Chinese: 我们初始化两个栈：stack 用于存储所有元素，min_stack 用于跟踪最小值。

2. Push Operation / 入栈操作

   def push(self, x: int) -> None:
      self.stack.append(x)
      if not self.min_stack or x <= self.min_stack[-1]:
          self.min_stack.append(x)

   • English: When pushing an element onto the stack, we also push it onto the min_stack if it's the smallest value seen so far.
   • Chinese: 当将元素推入 stack 时，如果它是到目前为止看到的最小值，我们也将其推入 min_stack。

3. Pop Operation / 出栈操作

   def pop(self) -> None:
      if self.stack[-1] == self.min_stack[-1]:
          self.min_stack.pop()
      self.stack.pop()

   • English: When popping an element from the stack, we also pop from the min_stack if the popped element is the current minimum.
   • Chinese: 当从 stack 弹出元素时，如果弹出的元素是当前最小值，我们也从 min_stack 中弹出。

4. Top Operation / 栈顶操作

   def top(self) -> int:
      return self.stack[-1]

   • English: The top method returns the top element of the stack.
   • Chinese: top 方法返回 stack 的栈顶元素。

5. GetMin Operation / 获取最小值操作

   def getMin(self) -> int:
      return self.min_stack[-1]

   • English: The getMin method returns the top element of the min_stack, which is the minimum value in the stack.
   • Chinese: getMin 方法返回 min_stack 的栈顶元素，即 stack 中的最小值。

Approach 2: Single Stack with Pair Elements / 单栈法（元素对）

This approach uses a single stack to store pairs of values. Each pair contains the actual value and the current minimum at the time of pushing.

这种方法使用单个栈来存储值对。每个对包含实际值和推入时的当前最小值。

Implementation / 实现

class MinStack:

    def __init__(self):
        self.stack = []

    def push(self, x: int) -> None:
        current_min = x if not self.stack else min(x, self.stack[-1][1])
        self.stack.append((x, current_min))

    def pop(self) -> None:
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1][0]

    def getMin(self) -> int:
        return self.stack[-1][1]

Explanation / 解释

1. Single Stack Initialization / 单栈初始化

   self.stack = []

   • English: We initialize a single stack that will store pairs of elements, where each pair contains the element and the current minimum.
   • Chinese: 我们初始化一个栈，该栈将存储元素对，每个对包含元素和当前最小值。

2. Push with Pair / 带对入栈

   def push(self, x: int) -> None:
      current_min = x if not self.stack else min(x, self.stack[-1][1])
      self.stack.append((x, current_min))

   • English: When pushing an element, we store it along with the minimum value up to that point in the stack.
   • Chinese: 推入元素时，我们将其与当前最小值一起存储在栈中。

3. Pop and Maintain Integrity / 弹出并保持完整性

   def pop(self) -> None:
      self.stack.pop()

   • English: The pop operation simply removes the top element pair from the stack.
   • Chinese: 弹出操作只是从栈中移除顶部元素对。

4. Retrieve Top Element / 获取栈顶元素

   def top(self) -> int:
      return self.stack[-1][0]

   • English: The top method returns the actual value stored at the top of the stack.
   • Chinese: top 方法返回存储在栈顶的实际值。

5. Retrieve Minimum Element / 获取最小元素

   def getMin(self) -> int:
      return self.stack[-1][1]

   • English: The getMin method returns the minimum value stored at the top of the stack, which reflects the minimum in the entire stack.
   • Chinese: getMin 方法返回存储在栈顶的最小值，反映整个栈中的最小值。

Recursive Approach / 递归方法

This problem does not naturally lend itself to a recursive approach, especially due to the nature of stack operations, which are inherently iterative.

这个问题不太适合递归方法，尤其是由于栈操作的性质，它们本质上是迭代的。

Complexity Analysis / 复杂度分析

• Time Complexity / 时间复杂度: O(1) for all operations (push, pop, top, getMin).
• Space Complexity / 空间复杂度: O(n), where n is the number of elements in the stack.

Key Concept / 关键概念

• Stack Management / 栈管理: The use of a second stack or paired elements allows efficient retrieval of the minimum element while maintaining constant-time complexity for all operations.
• 栈管理: 使用第二个栈或元素对能够在保持所有操作的常数时间复杂度的同时，高效地检索最小元素。

Summary / 总结

• English: The Min Stack problem showcases how stack data structures can be enhanced with auxiliary storage to support advanced operations like retrieving the minimum value efficiently.
• Chinese: Min Stack 问题展示了如何使用辅助存储来增强栈数据结构

，以支持像高效检索最小值这样的高级操作。

Tips / 提示

• English: Practice implementing different variations of stack-based problems to deepen your understanding of how stacks can be used in various scenarios.
• Chinese: 练习实现不同变体的基于栈的问题，以加深你对栈在各种场景中如何使用的理解。

Solution Template for Similar Questions / 提示

• English: Consider using additional stacks or paired elements when a problem involves maintaining a dynamic minimum or maximum in constant time.
• Chinese: 当问题涉及在常数时间内维护动态最小值或最大值时，考虑使用额外的栈或元素对。

5 More Similar Questions / 推荐5问题

1. LeetCode 232. Implement Queue using Stacks
2. LeetCode 225. Implement Stack using Queues
3. LeetCode 84. Largest Rectangle in Histogram
4. LeetCode 42. Trapping Rain Water
5. LeetCode 150. Evaluate Reverse Polish Notation

Recommended Resources / 推荐资源

• English: Practice problems that involve stack operations to build a strong understanding of how to manipulate and optimize stack-based algorithms.
• Chinese: 练习涉及栈操作的问题，以建立对如何操作和优化基于栈的算法的深刻理解。

Design Min Stack - Amazon Interview Question - Leetcode 155 - Python by NeetCode