原地栈

原地栈的定义、实现方式与典型应用

#algorithm #concept #growing #stack

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

前置概念: 栈

相关技巧: 单调栈, 双指针

原地栈 In-Place Stack

一句话定义

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

核心机制 / 工作原理

思路

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

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

什么时候用

题目要求 O(1) 额外空间（如原地算法题）
能证明复用的输入区域已经读取，且原值后续不再需要
典型场景：单调栈、表达式求值、括号匹配的变体

最小例子：原地消除相邻重复值

从左向右读取数组，用已经读过的前缀保存幸存者。top 表示逻辑栈长度；相邻相同值成对消除，例如 [1, 2, 2, 1, 3] 最后保留 [3]。

function cancelAdjacentPairsInPlace(values) {
  let top = 0;
  for (let read = 0; read < values.length; read++) {
    const value = values[read];
    if (top > 0 && values[top - 1] === value) {
      top--;
    } else {
      values[top++] = value;
    }
  }
  values.length = top;
  return values;
}

读取当前值后再写回，且 top 始终不超过 read + 1，因此不会覆盖尚未读取的元素。算法修改原数组，时间 O(n)、额外空间 O(1)；这里按严格相等比较值，不是深层对象去重。

原例创建了独立 stack 和 result 数组，实际是普通“右侧下一个更大元素”算法，不是原地栈；它也不是完整的 LeetCode 496 两数组查询接口。不能随意把输入后半段当作空闲区：那里可能还有未读取数据。

原地栈 vs 普通栈

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

边界与常见误解

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