最小栈

题面

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

实现 MinStack 类:

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

示例 1:

输入： ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]

输出： [null,null,null,null,-3,null,0,-2]

解释： MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.

提示：

• -231 <= val <= 231 - 1
• pop、top 和 getMin 操作总是在 非空栈 上调用 push, pop, top, and getMin最多被调用 3 104 次

分析

• 最小栈、最小队列、最小双端队列这类 “最小 XX” 数据结构的核心设计思路是：使用两个容器，一个主容器存储所有元素，一个辅助容器（也叫 “单调容器”）专门维护最小值的候选序列，保证辅助容器的头部始终是当前的最小值

  • 辅助容器需要保持单调递增（栈 / 队列 / 双端队列），这样头部就是最小值

  • 新增元素时，辅助容器会移除所有比新元素大的元素，再加入新元素，确保单调性

  • 删除元素时，只有当被删除的元素是辅助容器的头部（即当前最小值），才同步删除辅助容器的头部

• 最小栈的直观实现

  • 可以维护两个数组，一个数组表示栈，另一个表示栈中每个元素所对应的最小值
  • 此时，辅助栈（mininum）的每个位置，存储 “主队列对应位置及之前所有元素的最小值“

• 代码实现

  class MinStack {
  public:
      // 成员变量：两个双端队列，st 存所有元素，mininum 存对应位置的累积最小值
      std::deque<int> st;
      std::deque<int> mininum;
      
      // 构造函数：默认空实现即可，deque 会自动初始化
      MinStack() {}
  
      void push(int val) {
          // 1. 主队列尾部添加新元素
          st.push_back(val);
          // 2. 计算当前要存入辅助队列的最小值：
          //    - 若辅助队列为空，说明是第一个元素，当前最小值就是 val（这里代码用 INT_MAX 过渡，逻辑等价）
          //    - 若辅助队列非空，取辅助队列最后一个值（前n个元素的最小值）和当前val的较小值
          int cur_min = mininum.empty() ? INT_MAX : mininum.back();
          mininum.push_back(min(cur_min, val));
      }
  
      void pop() {
          // 3. 出栈时，主队列和辅助队列同步弹出尾部元素
          //    因为辅助队列的尾部对应主队列尾部的累积最小值，弹出后自然匹配新的栈状态
          st.pop_back();
          mininum.pop_back();
      }
  
      int top() { 
          // 4. 获取栈顶元素：直接返回主队列尾部
          return st.back(); 
      }
  
      int getMin() { 
          // 5. 获取最小值：直接返回辅助队列尾部（当前所有元素的累积最小值）
          return mininum.back(); 
      }
  };

• 以上实现中，辅助栈的大小与主栈相同，空间复杂度比较高，且辅助栈会存储大量重复的最小值，而是维护一个单调不减辅助栈（从栈顶到栈底）

  • push：若 val ≤ 辅助栈顶元素（或辅助栈为空），则将 val 压入辅助栈（保证栈顶是最小值）
  • pop：若弹出的元素 == 辅助栈顶元素（说明弹出的是当前最小值），则同步弹出辅助栈顶

• 为什么用 ≤ 而非 <？

  • 这是避免 bug 的关键！如果用 <，当入栈重复最小值时（如 push (3,3)）：
    • 辅助栈只会添加第一个 3，第二个 3 因不满足 < 不会添加；
    • 当弹出第一个 3 时，辅助栈同步弹出，此时主栈还有一个 3，但辅助栈为空，调用 getMin() 会崩溃
  • 用 ≤ 可以保证：有多少个最小值，辅助栈就存储多少个，弹出时精准匹配，无边界漏洞

• 代码实现

  class MinStack {
  public:
      // 主栈：存储所有元素
      std::deque<int> st;
      // 辅助单调栈：仅存储最小值候选，栈顶始终是当前最小值，保持单调不减
      std::deque<int> min_stack;
  
      MinStack() {}
  
      void push(int val) {
          // 1. 主栈正常添加元素
          st.push_back(val);
          
          // 2. 辅助栈：空 或 当前值 ≤ 栈顶值时，才添加（保证单调不减）
          // 关键：用 ≤ 而非 <，避免重复最小值丢失
          if (min_stack.empty() || val <= min_stack.back()) {
              min_stack.push_back(val);
          }
      }
  
      void pop() {
          // 1. 主栈弹出栈顶元素
          int popped_val = st.back();
          st.pop_back();
          
          // 2. 若弹出的是当前最小值（辅助栈顶），辅助栈同步弹出
          if (popped_val == min_stack.back()) {
              min_stack.pop_back();
          }
      }
  
      int top() {
          // 直接返回主栈栈顶
          return st.back();
      }
  
      int getMin() {
          // 直接返回辅助栈栈顶（当前最小值）
          return min_stack.back();
      }
  };

最小栈（O(1) 空间复杂度）

• 可以使用差值栈，来避免引入额外的时间复杂度

• 差值法的核心逻辑是：

  1. 栈中不直接存储原始元素，而是存储「当前元素 - 上一轮的最小值」的差值 diff；
  2. 用一个变量 min_val 实时记录当前栈中的最小值；
  3. 通过差值 diff 和 min_val 的反向计算，还原出原始元素，并动态更新 min_val：
     • 入栈 (push)：
       • 栈空时：min_val 设为当前元素，栈压入 0（因为 元素 - min_val = 0）；
       • 栈非空时：计算 diff = val - min_val，压入 diff；若 diff < 0，说明新元素比当前最小值更小，更新 min_val = val
     • 出栈 (pop)：
       • 弹出栈顶的 diff；若 diff < 0，说明弹出的是当前最小值，需要还原上一轮的最小值：min_val = min_val - diff（因为 diff = 新元素 - 旧min_val，所以 旧min_val = 新元素 - diff = min_val - diff）；
       • 若 diff ≥ 0，最小值不变
     • 获取栈顶 (top)：
       • 若栈顶 diff ≥ 0，栈顶原始值 = min_val + diff；
       • 若栈顶 diff < 0，栈顶原始值 = min_val（因为此时 diff 是“新最小值 - 旧最小值”，栈顶就是当前 min_val）
     • 获取最小值 (getMin)：直接返回 min_val 即可

• 代码实现

  #include <iostream>
  #include <stack>
  #include <stdexcept>
  
  class MinStack {
  private:
      std::stack<long long> diffStack; // 存储差值（用long long避免溢出）
      long long min_val;                // 记录当前栈的最小值
  
  public:
      MinStack() : min_val(0) {}
  
      // 入栈：存储 val - min_val 的差值
      void push(int val) {
          if (diffStack.empty()) {
              min_val = val;           // 栈空时，最小值就是当前元素
              diffStack.push(0LL);     // 差值为 0
          } else {
              long long diff = (long long)val - min_val; // 计算差值
              diffStack.push(diff);
              // 差值 < 0，说明新元素更小，更新最小值
              if (diff < 0) {
                  min_val = val;
              }
          }
      }
  
      // 出栈：根据差值还原上一轮的最小值
      void pop() {
          if (diffStack.empty()) {
              throw std::underflow_error("Stack is empty, cannot pop!");
          }
  
          long long diff = diffStack.top();
          diffStack.pop();
  
          // 差值 < 0，说明弹出的是当前最小值，需要还原旧最小值
          if (diff < 0) {
              min_val = min_val - diff;
          }
      }
  
      // 获取栈顶元素：通过差值和min_val还原原始值
      int top() {
          if (diffStack.empty()) {
              throw std::underflow_error("Stack is empty, no top element!");
          }
  
          long long diff = diffStack.top();
          // 差值 ≥ 0：原始值 = min_val + diff
          // 差值 < 0：原始值就是当前min_val（因为此时diff是新值-旧min，新值就是min_val）
          if (diff >= 0) {
              return static_cast<int>(min_val + diff);
          } else {
              return static_cast<int>(min_val);
          }
      }
  
      // 获取最小值：直接返回min_val
      int getMin() {
          if (diffStack.empty()) {
              throw std::underflow_error("Stack is empty, no minimum value!");
          }
          return static_cast<int>(min_val);
      }
  };

最小队列

• 最小队列需要支持：enqueue（入队）、dequeue（出队）、front（队首）、getMin（O (1) 获取最小值），且空间复杂度优于 “累积最小值” 的朴素实现

• 队列是先进先出（FIFO），而栈是先进后出，因此最小栈的 “单调栈” 思路不能直接复用：

  • 栈的弹出只在尾部，辅助栈只需维护尾部单调性；
  • 队列的弹出在头部，若辅助容器用普通栈 / 队列，无法高效维护头部的最小值

• 可以用单调双端队列（deque） 作为辅助容器：

  • 辅助 deque 保持单调递增（队首是当前最小值）；
  • 入队时：移除辅助 deque 尾部所有比新元素大的元素，再加入新元素（保证单调性）；
  • 出队时：若出队元素等于辅助 deque 队首（当前最小值），则同步弹出辅助 deque 队首

• 代码实现

  class MinQueue {
  public:
      // 主队列：存储所有元素
      std::deque<int> main_queue;
      // 辅助单调双端队列：队首是当前最小值，保持单调递增
      std::deque<int> min_deque;
  
      MinQueue() {}
  
      // 入队操作
      void enqueue(int val) {
          // 1. 主队列尾部添加元素
          main_queue.push_back(val);
  
          // 2. 辅助队列：移除尾部所有比当前值大的元素，保证单调递增
          // 核心：只保留“可能成为最小值”的候选元素
          while (!min_deque.empty() && min_deque.back() > val) {
              min_deque.pop_back();
          }
          min_deque.push_back(val);
      }
  
      // 出队操作（返回出队元素）
      int dequeue() {
          if (main_queue.empty()) {
              throw runtime_error("MinQueue is empty, cannot dequeue!");
          }
  
          // 1. 主队列弹出队首元素
          int dequeued_val = main_queue.front();
          main_queue.pop_front();
  
          // 2. 若弹出的是当前最小值（辅助队列队首），同步弹出
          if (dequeued_val == min_deque.front()) {
              min_deque.pop_front();
          }
  
          return dequeued_val;
      }
  
      // 获取队首元素
      int front() {
          if (main_queue.empty()) {
              throw runtime_error("MinQueue is empty, no front element!");
          }
          return main_queue.front();
      }
  
      // O(1) 获取当前队列最小值
      int getMin() {
          if (min_deque.empty()) {
              throw runtime_error("MinQueue is empty, no minimum value!");
          }
          return min_deque.front();
      }
  };

最小双端队列

• 最小双端队列（MinDeque）需要支持：

  • append(val)：尾部添加元素；
  • appendleft(val)：头部添加元素；
  • pop()：尾部删除元素（返回值）；
  • popleft()：头部删除元素（返回值）；
  • getMin()：O (1) 获取当前最小值；
  • 所有操作需保证均摊 O (1) 时间复杂度，空间复杂度优于 “累积最小值” 的朴素实现

• 双端队列支持头部 / 尾部双向操作，因此辅助容器必须满足：

  1. 能高效维护双向操作后的最小值；
  2. 辅助容器仍用单调递增的双端队列（队首是最小值）；
  3. 双向添加时需分别维护单调性，双向删除时需精准同步辅助容器

• 代码实现

  #include <deque>
  #include <stdexcept>
  using namespace std;
  
  class MinDeque {
  public:
      // 主双端队列：存储所有元素
      std::deque<int> main_deque;
      // 辅助单调双端队列：队首始终是当前最小值，保持严格单调递增（或非递减）
      std::deque<int> min_deque;
  
      MinDeque() {}
  
      // ========== 双向添加操作 ==========
      // 尾部添加元素
      void append(int val) {
          // 1. 主队列尾部添加元素
          main_deque.push_back(val);
  
          // 2. 辅助队列：移除尾部所有 ≥ 当前值的元素（保证单调递增）
          // 核心：只保留“可能成为最小值”的候选，避免冗余
          while (!min_deque.empty() && min_deque.back() > val) {
              min_deque.pop_back();
          }
          min_deque.push_back(val);
      }
  
      // 头部添加元素
      void appendleft(int val) {
          // 1. 主队列头部添加元素
          main_deque.push_front(val);
  
          // 2. 辅助队列：移除头部所有 ≥ 当前值的元素（新元素在头部，可能成为更小值）
          // 注意：头部添加时，对比辅助队列的头部而非尾部！
          while (!min_deque.empty() && min_deque.front() > val) {
              min_deque.pop_front();
          }
          min_deque.push_front(val);
      }
  
      // ========== 双向删除操作 ==========
      // 尾部删除元素（返回删除值）
      int pop() {
          if (main_deque.empty()) {
              throw runtime_error("MinDeque is empty, cannot pop!");
          }
  
          // 1. 主队列尾部弹出元素
          int popped_val = main_deque.back();
          main_deque.pop_back();
  
          // 2. 若弹出的是辅助队列尾部元素（当前最小值候选），同步弹出
          if (popped_val == min_deque.back()) {
              min_deque.pop_back();
          }
  
          return popped_val;
      }
  
      // 头部删除元素（返回删除值）
      int popleft() {
          if (main_deque.empty()) {
              throw runtime_error("MinDeque is empty, cannot popleft!");
          }
  
          // 1. 主队列头部弹出元素
          int popped_val = main_deque.front();
          main_deque.pop_front();
  
          // 2. 若弹出的是辅助队列头部元素（当前最小值），同步弹出
          if (popped_val == min_deque.front()) {
              min_deque.pop_front();
          }
  
          return popped_val;
      }
  
      // ========== 核心查询操作 ==========
      // O(1) 获取当前最小值
      int getMin() {
          if (min_deque.empty()) {
              throw runtime_error("MinDeque is empty, no minimum value!");
          }
          return min_deque.front();
      }
  
      // 可选：获取当前队列元素（方便测试）
      std::deque<int> getElements() const {
          return main_deque;
      }
  };

总结

• 三者的核心目标一致：在常规数据结构基础上，支持 O (1) 时间复杂度获取最小值，且所有增删操作均摊 O (1) 时间，空间复杂度优于 “累积最小值” 的朴素实现

• 核心设计思路均为：主容器 + 单调辅助容器（辅助容器维护最小值候选，保证头部 / 尾部是当前最小值）

  维度	最小栈（MinStack）	最小队列（MinQueue）	最小双端队列（MinDeque）
  主容器类型	栈（deque 模拟，仅尾部操作）	队列（deque 模拟，头部出、尾部入）	双端队列（deque，头部 / 尾部双向操作）
  辅助容器类型	单调栈（deque）	单调双端队列（deque）	单调双端队列（deque）
  辅助容器单调性	单调不减（栈顶是最小值）	单调递增（队首是最小值）	单调递增（队首是最小值）
  新增元素逻辑	1. 主栈尾部添加；2. 仅当 val ≤ 栈顶 时，辅助栈尾部添加（无循环）。	1. 主队列尾部添加；2. 移除辅助队列尾部所有 > val 的元素，再尾部添加（有循环）。	- 尾部添加：同最小队列；- 头部添加：移除辅助队列头部所有 > val 的元素，再头部添加（有循环）。
  删除元素逻辑	1. 主栈尾部弹出；2. 若弹出值 == 辅助栈顶，辅助栈尾部弹出。	1. 主队列头部弹出；2. 若弹出值 == 辅助队列首，辅助队列头部弹出。	- 尾部删除：若弹出值 == 辅助队列尾，辅助队列尾部弹出；- 头部删除：若弹出值 == 辅助队列首，辅助队列头部弹出。
  获取最小值	辅助栈顶（O (1)）	辅助队列首（O (1)）	辅助队列首（O (1)）
  时间复杂度	所有操作纯 O (1)（无循环）	enqueue 均摊 O (1)，其余纯 O (1)	append/appendleft 均摊 O (1)，其余纯 O (1)
  空间复杂度	最好 O (1)，最坏 O (n)	最好 O (1)，最坏 O (n)	最好 O (1)，最坏 O (n)
  核心难点	无（逻辑最简单）	处理 FIFO 特性，辅助容器需双端队列 + 循环移除冗余元素	双向操作的单调性维护（头部 / 尾部需分别处理）

• 输入操作：添加5 → 添加3 → 添加4 → 删除头部/尾部 → 获取最小值

  结构	操作步骤	主容器状态	辅助容器状态	最小值
  最小栈	push(5) → push(3) → push(4) → pop() → getMin()	[5,3]（弹出 4）	[5,3]（无弹出）	3
  最小队列	enqueue(5) → enqueue(3) → enqueue(4) → dequeue() → getMin()	[3,4]（弹出 5）	[3,4]（无弹出）	3
  最小双端队列	append(5) → appendleft(3) → append(4) → popleft() → getMin()	[5,4]（弹出 3）	[5,4]（弹出 3）	4

• 使用场景

  结构	核心适用场景	典型应用
  最小栈	需频繁获取栈内最小值的场景（后进先出）	表达式求值、回溯算法、栈溢出监控
  最小队列	需频繁获取队列内最小值的场景（先进先出）	滑动窗口最小值、任务调度优先级
  最小双端队列	需双向操作且频繁获取最小值的场景	双端滑动窗口、缓存淘汰策略

最大栈

• 显然可以用与最小栈的思路来实现，另一种思路是利用懒删除堆

  • 普通栈：存储所有元素，维护 LIFO 顺序；
  • 大顶堆：存储「元素值 + 时间戳」（时间戳保证元素唯一性），维护最大值；
  • 哈希集合 / 计数器：标记 “已被栈弹出但仍在堆中的失效元素”；
  • 时间戳：区分相同值的不同元素（比如栈中压入两个 5，需用时间戳标记为 5_1、5_2）

• 代码实现

  #include <iostream>
  #include <stack>
  #include <queue>
  #include <unordered_map>
  using namespace std;
  
  class MaxStack {
  private:
      // 栈：存储 (元素值, 时间戳)，维护LIFO顺序
      stack<pair<int, int>> data_stack;
      // 大顶堆：存储 (元素值, 时间戳)，维护最大值（懒删除）
      priority_queue<pair<int, int>> max_heap;
      // 懒删除标记：记录已失效的 (值, 时间戳) 数量（避免重复删除）
      unordered_map<int, unordered_map<int, int>> deleted;
      int timestamp = 0; // 唯一时间戳，区分相同值的元素
  
      // 核心：懒删除——清理堆顶所有失效元素
      void lazyRemove() {
          while (!max_heap.empty()) {
              auto [val, ts] = max_heap.top();
              // 检查该元素是否已被标记为删除
              if (deleted.count(val) && deleted[val].count(ts) && deleted[val][ts] > 0) {
                  // 失效：弹出堆顶，并减少标记计数
                  deleted[val][ts]--;
                  if (deleted[val][ts] == 0) {
                      deleted[val].erase(ts); // 清理空条目，节省空间
                      if (deleted[val].empty()) {
                          deleted.erase(val);
                      }
                  }
                  max_heap.pop();
              } else {
                  // 堆顶有效，停止清理
                  break;
              }
          }
      }
  
  public:
      MaxStack() {}
  
      // 压入元素：栈和堆同时添加，时间戳自增
      void push(int x) {
          data_stack.emplace(x, timestamp);
          max_heap.emplace(x, timestamp);
          timestamp++;
      }
  
      // 弹出栈顶：标记该元素失效，不立刻删除堆中元素
      int pop() {
          if (data_stack.empty()) {
              throw runtime_error("Stack is empty!");
          }
          auto [val, ts] = data_stack.top();
          data_stack.pop();
          // 标记该元素为失效（懒删除的核心：只标记，不清理堆）
          deleted[val][ts]++;
          return val;
      }
  
      // 获取栈顶元素
      int top() {
          if (data_stack.empty()) {
              throw runtime_error("Stack is empty!");
          }
          return data_stack.top().first;
      }
  
      // 获取最大值：先懒删除失效元素，再返回堆顶
      int getMax() {
          if (data_stack.empty()) {
              throw runtime_error("Stack is empty!");
          }
          lazyRemove(); // 清理堆顶失效元素
          return max_heap.top().first;
      }
  
      // 进阶：弹出最大值（同样基于懒删除）
      int popMax() {
          if (data_stack.empty()) {
              throw runtime_error("Stack is empty!");
          }
          // 先清理堆顶失效元素，找到有效最大值
          lazyRemove();
          auto [max_val, max_ts] = max_heap.top();
          max_heap.pop(); // 堆中直接弹出（已确认有效）
  
          // 栈中找到该最大值元素并弹出，同时标记后续可能的重复值
          stack<pair<int, int>> temp;
          // 弹出栈顶直到找到目标元素
          while (data_stack.top().second != max_ts) {
              temp.push(data_stack.top());
              data_stack.pop();
          }
          data_stack.pop(); // 弹出最大值元素
  
          // 把临时栈元素压回（无需重新入堆，堆中已有这些元素）
          while (!temp.empty()) {
              data_stack.push(temp.top());
              temp.pop();
          }
  
          return max_val;
      }
  };