[!info] related notes 算法面试题型 MOC

• 前置概念: 栈
• 相关技巧: 单调栈, 双指针

原地栈 In-Place Stack

一句话定义

原地栈是在不额外分配栈空间的情况下，直接利用输入数组本身作为栈来操作的技巧，常用于算法题中节省空间。

核心机制 / 工作原理

思路

不创建独立的 stack = []，而是复用已有的数组，通过一个指针/索引标记栈顶位置：

• stackIndex 初始指向数组某个位置
• 入栈：写入 arr[stackIndex]，然后 stackIndex++
• 出栈：stackIndex--，读取 arr[stackIndex]
• 判空：stackIndex === 初始值

什么时候用

• 题目要求 O(1) 额外空间（如原地算法题）
• 输入数组有未使用的空间可以当作栈底
• 典型场景：单调栈、表达式求值、括号匹配的变体

最小例子

LeetCode 496: 下一个更大元素 I

给定数组 nums，对每个元素找到右边第一个比它大的值。用原地栈 + 单调递减栈：

function nextGreaterElements(nums) {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack = []; // 存索引，栈底到栈顶递减

  for (let i = 0; i < n; i++) {
    while (stack.length && nums[i] > nums[stack[stack.length - 1]]) {
      result[stack.pop()] = nums[i];
    }
    stack.push(i);
  }
  return result;
}

如果题目要求 O(1) 额外空间，可以将 nums 的后半段或未使用位置当作栈底，用一个索引变量标记栈顶，避免额外数组。

原地栈 vs 普通栈

维度	普通栈	原地栈
空间	O(n) 额外数组	O(1) 额外空间
可读性	高	较低
适用场景	通用	空间受限的算法题

边界与常见误解

• “原地栈是一种数据结构” — 不是。它是一种空间优化技巧，底层还是栈的 LIFO 操作。
• “原地栈 = 单调栈” — 两者不同。单调栈是栈的内容保持单调性（用于”下一个更大/更小元素”类问题），原地栈强调的是空间复用。两者可以组合使用。
• 覆盖原数据 — 原地栈会修改输入数组。如果题目不允许修改输入，就不能用原地栈。
• 索引管理 — 原地栈最容易出错的地方是栈顶指针的维护，需要仔细处理边界。

related notes

• 栈
• 单调栈
• 算法面试题型 MOC