空间复杂度优化

4.2 空间复杂度优化

本节摘要：时间优化到头之后，空间往往是第二战场。本节系统整理三板斧——原地操作用交换替代辅助数组、滚动变量砍掉历史依赖、二维表压成一行——并讲清哪些结构能压、哪些不能压、压缩换来了什么又失去了什么。

时间的账之后是空间的账

上一节守住了正确性，本节面对进化链的下半场：同样 O(n) 时间的两个解，一个吃 O(n) 空间、一个 O(1)，面试官追问"空间还能再省吗"时，答得上来才说明你真的理解了状态依赖。空间优化的第一原则来自第二章动态规划一节的结尾：只依赖固定窗口的的历史状态，窗口外就能丢。本节把这句话展开成三个层次。

一、第一板斧：原地操作

最直接的空间浪费是"为了方便新开一份拷贝"。典型场景是数组去重、移动零、删除元素——朴素解法都爱开个结果数组。原地解法用读写双指针：读指针探路，写指针只接收要保留的元素，写过的区间就是答案区。第一章双指针一节的去重代码就是标准模板。原地交换的另一个代表是数组轮转：把数组右移 k 位，三次反转即可完成——先整体反转，再反转前 k 位，再反转剩余部分，全程 O(1) 空间。

def rotate(nums, k):
    n = len(nums)
    k %= n                      # k 可能大于长度
    def rev(lo, hi):
        while lo < hi:
            nums[lo], nums[hi] = nums[hi], nums[lo]
            lo, hi = lo + 1, hi - 1
    rev(0, n - 1)
    rev(0, k - 1)
    rev(k, n - 1)

a = [1, 2, 3, 4, 5, 6, 7]
rotate(a, 3)
print(a)     # 输出 [5, 6, 7, 1, 2, 3, 4]
​

原地的代价要想清楚：输入被破坏了。若调用方还需要原数组，原地就是伪优化；快速排序选原地而牺牲稳定性、归并排序保稳定而付 O(n) 辅助数组，正是同一笔交易的两面。

二、第二板斧：滚动变量

斐波那契类问题（含爬楼梯）是教科书案例：状态 f(i) 只依赖 f(i 减一) 与 f(i 减二)，存整个数组纯属浪费，两个变量滚动前进，O(n) 空间变 O(1)。第二章已给出代码，本节补充它的推广判据：依赖窗口宽度是几，就留几个变量。宽度为常数时空间从 O(n) 降到 O(1)。

三、第三板斧：二维表压一行

动态规划的二维表是最常见的空间大户。以零钱兑换的变式为例——0-1 背包：n 件物品各有重量与价值，容量 W 的背包求最大价值。朴素写法 dp[i][w] 表示考虑前 i 件、容量 w 的最优值，空间 n 乘 W。观察依赖关系：第 i 行只依赖第 i 减一行，且依赖的是同一列及更左列——于是二维表压成一行，但有个致命细节：0-1 背包（每件只用一次）必须让容量从大到小遍历，否则本行左侧的更新会污染"上一行"的语义，物品被重复选用；完全背包（每件无限用）恰恰要从小到大遍历。一行代码的遍历方向，区分了两种背包——这是空间优化里最经典、最高频的考点。

def knapsack_01(weights, values, W):
    dp = [0] * (W + 1)
    for wt, val in zip(weights, values):
        for w in range(W, wt - 1, -1):    # 容量倒序，保证每件只用一次
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[W]

def knapsack_complete(weights, values, W):
    dp = [0] * (W + 1)
    for wt, val in zip(weights, values):
        for w in range(wt, W + 1):        # 容量正序，允许重复选用
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[W]

print(knapsack_01([1, 3, 4], [15, 30, 45], 6))       # 输出 60（选两件：3 与 3 不行，取 1 加 4 之外最优）
print(knapsack_complete([1, 3, 4], [15, 30, 45], 6)) # 输出 90（重复选用 3 加 3）
​

空间压缩三板斧全景

四、不能压的与不该压的

有两类"压缩"是陷阱。递归栈是隐性空间，把递归改成迭代能砍掉它，但如果算法本质需要栈（如树的迭代遍历），显式栈照样 O(n)——省的只是系统栈上限，不是复杂度。另一个陷阱是莫里斯遍历那类极致压缩：空间 O(1) 却临时改树结构，多线程或调用方持有引用时是事故源。选型判据与全册一致：先正确、再时间、后空间；压缩永远放最后一步，且必须有对拍兜底。

四、两道进阶案例

案例一，原地删除有序数组的重复项并要求每个元素至多保留两次。在读写双指针模板上只改一处判定：当前元素是否与慢指针前第二个元素相同，相同则跳过、不同则写入。判定从"与前一个比"改成"与前第二个比"，就实现了"至多保留两次"的泛化——把数字二换成参数 k，模板直接支持保留至多 k 次。这个泛化演示了原地双指针的真正弹性：写入条件是策略层，读写框架是结构层，两层解耦后变化只发生在一行。

def remove_duplicates_twice(nums):
    slow = 0
    for x in nums:
        if slow < 2 or x != nums[slow - 2]:
            nums[slow] = x
            slow += 1
    return slow

a = [1, 1, 1, 2, 2, 3]
k = remove_duplicates_twice(a)
print(k, a[:k])    # 输出 5 [1, 1, 2, 2, 3]
​

案例二，生命游戏的原地进化：棋盘每格生死按邻居数量同步更新，朴素解法复制整块棋盘存下一状态，空间 O(m 乘 n)。观察状态取值只有两种，用"第二位暂存未来、第一位表示现在"的编码：要死的活人标记成二，要复活的死人标记成三，全盘标记完成后再统一解码。空间降为 O(1)，代价是代码可读性下降与"并行更新"语义被编码技巧掩盖——面试中先给复制版再说清编码压缩，是标准答法。两个案例共同的教训：空间优化经常不是换个数据结构，而是重新审视"信息到底存了几份"，冗余的那一份找到安全的方式复用掉即可。复用的安全性要现场论证——第二位编码不会与现有状态混淆，这是能压的前提。

本节要点回顾

• 第一原则：只依赖固定窗口的状态可以丢，窗口外的空间全部可省；
• 原地操作先问一句：调用方还需要原数据吗？需要就不是优化是破坏；
• 滚动变量看窗口宽度：宽度常数则空间常数；
• 背包遍历方向：0-1 倒序防重复选用，完全背包正序允许复用，一行代码定乾坤；
• 递归改迭代省的是栈上限，本质需要栈的算法空间复杂度不变。

下一节把进化链搬进真实系统：LRU 缓存、任务调度、海量统计——刷过的每个结构都能挂到一个真实组件上。