设计一个支持增量操作的栈 题目描述 设计一个栈数据结构，除了支持常规的栈操作（push、pop、top）外，还需要支持一个增量操作 increment(k, val) ，该操作会将栈底部的 k 个元素的值都增加 val 。如果栈中元素个数小于 k ，则将所有元素都增加 val 。要求所有操作的时间复杂度为 O(1)。 解题过程 1. 问题分析 常规栈的 push、pop、top 操作都是 O(1) 时间复杂度的。但增量操作 increment(k, val) 如果直接实现，需要修改栈底部 k 个元素，最坏情况下需要 O(n) 时间（当 k 接近 n 时），不符合题目要求。因此，我们需要一种延迟更新的机制，将增量操作的影响推迟到元素被访问（pop 或 top）时再应用。 2. 核心思路：延迟更新 我们可以使用两个栈来辅助： 一个主栈 stack 用于存储实际的值。 一个增量栈 inc 用于记录延迟的增量操作。 inc[i] 表示从栈底到位置 i 的所有元素需要累加的增量值。 但更高效的做法是只记录增量操作的差异。具体来说： 我们使用一个数组或链表作为栈的结构。 额外维护一个数组 add ， add[i] 表示从栈底到第 i 个元素（包括 i）这一段的增量值。 当执行 increment(k, val) 时，我们只需要更新 add 数组中的两个位置（实际上是栈的索引），而不需要修改栈中的每个元素。 3. 详细设计 我们使用一个数组 data 来模拟栈，并维护栈顶指针 top （指向下一个可插入位置）。同时，我们维护一个等长的数组 add ，用于记录增量。 关键点在于： 当执行 increment(k, val) 时： 令 idx = min(k, top) - 1 ，即受影响的最深位置（栈底索引为 0，栈顶索引为 top-1 ）。 将 add[idx] 增加 val 。这样，当我们后续访问某个元素时，可以通过累加从该位置到栈顶的增量来得到最终值。 但这样在 pop 时，我们需要知道从当前元素到栈顶的所有增量之和，如果每次都从头累加，最坏情况是 O(n)。为了保持 O(1)，我们需要另一种策略： 差分数组 。 4. 差分数组优化 我们使用一个差分数组 diff ，其中 diff[i] 表示 add[i] 与 add[i-1] 的差值（ add[-1] 视为 0）。这样： increment(k, val) 操作： 令 idx = min(k, top) - 1 。 将 diff[idx] 增加 val 。 当我们需要知道第 i 个位置的累计增量时， add[i] = diff[0] + diff[1] + ... + diff[i] 。这又变成了 O(n) 的累加。 为了 O(1) 地获取任意位置的累计增量，我们可以在 pop 时动态维护一个累计变量 sum ，从栈顶向栈底累加 diff 。但这样 pop 操作就不是 O(1) 了。我们需要更巧妙的做法。 5. 最终方案：惰性传播 我们维护一个辅助栈 inc ，其大小与主栈相同。 inc[i] 表示 以位置 i 为起点，向栈底方向的增量值 。更准确地说： 当执行 increment(k, val) 时： 令 idx = min(k, top) - 1 。 如果 idx >= 0 ，则将 inc[idx] 增加 val 。 当执行 pop() 时： 弹出栈顶元素 data[top-1] 和对应的 inc[top-1] 。 如果 inc[top-1] 不为 0，我们将这个增量值“传播”到下一个元素（即新的栈顶元素 top-2 ）上： inc[top-2] += inc[top-1] 。 然后返回 data[top-1] + 累计增量 （但注意，由于传播机制，弹出元素时它已经携带了所有该加的值）。 实际上，我们可以简化：只用一个 inc 数组，并在 pop 时进行传播。 top 操作也需要类似处理，但要注意不能修改栈状态。 6. 具体实现步骤 我们使用一个动态数组（如 vector）来存储数据，并用一个指针 top 表示栈顶位置。同时，我们维护一个等长的 inc 数组。 初始化 ：创建空数组 data 和 inc ， top = 0 。 push(val) ：将 val 放入 data[top] ， inc[top] = 0 ，然后 top++ 。 pop() ： 如果 top == 0 ，栈空，报错。 top-- 。 如果 top > 0 ，将当前栈顶元素的增量传播给新的栈顶元素： inc[top-1] += inc[top] 。 返回 data[top] + inc[top] （注意，此时 top 已指向被弹出元素的位置）。 top() ： 如果 top == 0 ，栈空，报错。 返回 data[top-1] + inc[top-1] 。 increment(k, val) ： 如果 top == 0 ，直接返回（无元素可增）。 令 idx = min(k, top) - 1 。 将 inc[idx] 增加 val 。 7. 时间复杂度分析 push: O(1) pop: O(1)（虽然有一个加法操作，但是常数时间） top: O(1) increment: O(1) 所有操作都满足 O(1) 时间复杂度。 8. 示例演示 假设依次执行： push(1); push(2); push(3); data = [ 1,2,3], inc = [ 0,0,0 ], top=3 increment(2, 100); k=2, idx=min(2,3)-1=1, inc[ 1] +=100 → inc=[ 0,100,0 ] top() → 返回 data[ 2]+inc[ 2 ]=3+0=3 pop() → top-- → top=2 inc[ 1] += inc[ 2] → inc[ 1 ]=100+0=100 返回 data[ 2]+inc[ 2 ]=3+0=3 data=[ 1,2], inc=[ 0,100 ], top=2 top() → 返回 data[ 1]+inc[ 1 ]=2+100=102 pop() → top-- → top=1 inc[ 0] += inc[ 1] → inc[ 0 ]=0+100=100 返回 data[ 1]+inc[ 1 ]=2+100=102 data=[ 1], inc=[ 100 ], top=1 top() → 返回 data[ 0]+inc[ 0 ]=1+100=101 通过这个例子，你可以看到增量操作被正确地延迟应用到了元素被访问的时候。