设计一个支持增量操作的栈 题目描述 设计一个栈，除了支持常规的压栈（push）、弹栈（pop）、查看栈顶元素（top）操作外，还需要支持一个增量操作（increment）。increment操作接受两个参数：k和val，表示从栈底开始的k个元素（如果栈中元素少于k个，则对所有元素操作）都增加val。要求所有操作的时间复杂度都是O(1)。 解题思路 常规的栈操作本身是O(1)的，但increment操作如果直接遍历栈底k个元素，时间复杂度为O(k)，不满足要求。为了达到O(1)的增量操作，我们需要采用惰性更新的思想，将增量操作记录下来，等到元素被弹出时再应用这些增量。 详细步骤 数据结构设计 使用一个数组（或列表） stack 来存储栈的元素。 使用另一个数组（或列表） inc 来记录增量操作。 inc[i] 表示从栈底到位置i（包括i）的所有元素需要累加的增量总和。 维护一个变量 size 表示当前栈中元素的数量。 push操作 将新元素压入 stack 。 在 inc 数组的对应位置（即 size 位置）初始化为0，因为新元素还没有受到任何增量操作的影响。 增加 size 。 pop操作 如果栈为空，返回错误。 否则，需要先计算当前栈顶元素的实际值。由于 inc[size-1] 记录了从栈底到栈顶元素的所有增量总和，所以实际值为 stack[size-1] + inc[size-1] 。 但注意：这个增量值只作用于当前元素，而栈顶下面的元素可能还有未应用的增量。因此，在弹出栈顶元素前，需要将 inc[size-2] （如果存在）加上 inc[size-1] ，这样栈顶下面的元素在将来被弹出时，会继承这个增量。 最后，弹出 stack 和 inc 的栈顶元素，并减少 size 。 top操作 类似于pop，但不弹出元素。直接返回 stack[size-1] + inc[size-1] 。 increment操作 确定实际需要增量的元素数量 m = min(k, size) 。 将增量 val 加到 inc[m-1] 上。因为 inc[m-1] 记录了从栈底到第m个元素的所有增量，这样当这些元素被弹出时，会通过pop操作中的传递机制正确应用增量。 举例说明 假设依次执行以下操作： push(1) push(2) increment(2, 100) // 栈底2个元素各加100 push(3) increment(2, 50) // 栈底2个元素各加50（此时栈有3个元素，栈底2个是1和2） pop() // 弹出3 pop() // 弹出2 pop() // 弹出1 执行过程： 操作1后：stack = [ 1], inc = [ 0 ], size=1 操作2后：stack = [ 1,2], inc = [ 0,0 ], size=2 操作3：k=2, val=100 -> inc[ 1] += 100 → inc = [ 0,100 ] 操作4后：stack = [ 1,2,3], inc = [ 0,100,0 ], size=3 操作5：k=2, val=50 -> inc[ 1] += 50 → inc = [ 0,150,0 ] 操作6（pop）： 栈顶索引=2，实际值=3+0=3 将inc[ 1] += inc[ 2] → inc = [ 0,150,0]（无变化，因为inc[ 2 ]=0） 弹出后：stack = [ 1,2], inc = [ 0,150 ], size=2 操作7（pop）： 栈顶索引=1，实际值=2+150=152 将inc[ 0] += inc[ 1] → inc = [ 150,150 ] 弹出后：stack = [ 1], inc = [ 150 ], size=1 操作8（pop）： 栈顶索引=0，实际值=1+150=151 弹出后栈空 最终弹出顺序：3, 152, 151，符合预期（1和2分别增加了100+50=150）。