设计一个支持增量操作的栈 -

题目

设计一个支持增量操作的栈

信息

类型：问答
难度：⭐⭐

考点

栈设计,差分数组,时间复杂度优化

快速回答

设计一个支持 push、pop、top 和增量操作的自定义栈：

使用数组存储栈元素，维护差分数组记录增量
push：栈未满时压入元素，差分数组对应位置初始化为0
pop：弹出栈顶元素时，将当前差分值加到元素上，并将增量传递给下一个位置
increment：修改栈底 k 个元素时，只需更新差分数组指定位置
时间复杂度：push/pop O(1)，increment O(1)

## 解析

问题描述

设计一个支持以下操作的栈：

CustomStack(int maxSize)：初始化栈
void push(int x)：压入元素（栈满时忽略）
int pop()：弹出栈顶元素（栈空返回-1）
void increment(int k, int val)：栈底 k 个元素增加 val（k>栈大小时更新全部元素）

核心原理

使用差分数组优化增量操作：

维护两个数组：stack存储原始值，diff存储差分值
diff[i]表示从位置 i 到 i+1 的增量（位置 i 的元素需要加的值）
增量操作时：diff[min(k-1, n-1)] += val
弹出操作时：
- 元素值 = stack.pop() + diff[top]
- 将diff[top]传递给diff[top-1]（若存在）
- 重置diff[top] = 0并弹出

代码实现（Python）

class CustomStack:
    def __init__(self, maxSize: int):
        self.stack = []
        self.diff = []  # 差分数组
        self.maxSize = maxSize

    def push(self, x: int) -> None:
        if len(self.stack) < self.maxSize:
            self.stack.append(x)
            self.diff.append(0)

    def pop(self) -> int:
        if not self.stack: return -1
        top = len(self.stack) - 1
        # 传递增量给前一个元素
        if top > 0:
            self.diff[top-1] += self.diff[top]
        # 计算实际值并弹出
        res = self.stack.pop() + self.diff.pop()
        return res

    def increment(self, k: int, val: int) -> None:
        if self.stack:
            idx = min(k, len(self.stack)) - 1  # 关键：取有效索引
            self.diff[idx] += val

最佳实践

空间优化：差分数组与栈同步增长，空间复杂度 O(n)
时间复杂度：所有操作均摊 O(1)
边界处理：
- 栈空时 pop 返回 -1
- 栈满时 push 忽略
- k>栈大小时取实际长度

常见错误

未传递增量：pop 时忘记将diff[top]传递给前一个元素
索引越界：increment 中直接使用k-1未考虑栈实际大小
差分数组未初始化：push 时忘记给diff添加初始值 0
增量累加错误：increment 中使用赋值=而非累加+=

扩展知识

差分数组应用场景：区间修改（如 LeetCode 370.区间加法）
对比方案：暴力法每次 increment 需 O(k) 时间，不适用于频繁操作
变种问题：支持中间元素修改时可结合线段树（时间复杂度 O(log n)）
实际应用：游戏中的批量状态更新、事务性操作的回滚栈