实现一个支持增量操作的栈 题目描述 ：设计一个栈，除了支持常规的入栈（push）、出栈（pop）、查看栈顶元素（top）操作外，还需要支持一个增量操作 increment(k, val) ，该操作会将栈底开始的 k 个元素（即最老的 k 个元素）都增加 val 。如果栈中元素个数小于 k ，则将所有元素都增加 val 。要求所有操作的时间复杂度为O(1)。 解题思路 ： 常规栈的push、pop、top操作都是O(1)的，但增量操作如果直接遍历栈底k个元素修改，时间复杂度为O(k)，不符合要求。因此，我们需要一种惰性更新的机制，将增量操作延迟到元素被访问（pop或top）时再应用。 核心思想 ：使用两个栈，一个栈 data 存储实际元素，另一个栈 inc 存储增量操作的累积值。 inc 栈的每个位置对应 data 栈相同位置的元素从该位置到栈底所有增量操作的总和（但仅在元素被访问时才应用）。 详细步骤 ： 数据结构设计 ： data 栈：存储实际压入的元素值。 inc 栈：存储增量操作的累积值，与 data 栈一一对应。 inc[i] 表示从栈底到 data[i] 这个位置，所有增量操作应用到 data[i] 上的总和（但尚未实际加到 data[i] 上）。 push操作 ： 将新元素压入 data 栈。 在 inc 栈中压入0，表示新元素目前没有累积的增量。 increment操作 ： 设当前栈大小为 n ，取 k = min(k, n) 。 如果栈非空（ n > 0 ），将 inc 栈中第 min(k, n) - 1 位置（即栈底向上第k个元素在 inc 栈中的索引）的值增加 val 。这样，这个增量会随着后续pop操作传播到更靠近栈顶的元素。 注意： inc 栈的索引从栈底（0）到栈顶（n-1）。我们只需要在 inc[k-1] 上累加 val ，因为当pop到 k-1 位置时，这个增量会被应用到该元素，并继续向上传播。 pop操作 ： 如果栈空，返回异常或特定值。 弹出 data 栈顶元素，记为 value 。 弹出 inc 栈顶的累积增量，记为 delta （这个 delta 是当前元素对应的增量）。 实际返回值为 value + delta （因为 delta 包含了所有需要应用到该元素的增量）。 如果 inc 栈非空，将新的栈顶元素的累积增量加上 delta （将增量传播到下一个元素）。 top操作 ： 类似pop，但不弹出元素。返回 data.top() + inc.top() 。 举例说明 ： 初始化： data = [] , inc = [] push(1): data = [1] , inc = [0] push(2): data = [1, 2] , inc = [0, 0] increment(2, 100): k=2, n=2, 修改 inc[2-1]=inc[1] ，增加100 → inc = [0, 100] increment(1, 50): k=1, n=2, 修改 inc[1-1]=inc[0] ，增加50 → inc = [50, 100] pop(): value = data.pop() = 2 , delta = inc.pop() = 100 返回值 = 2 + 100 = 102 传播增量： inc 栈顶原为50，现在变为50 + 100 = 150 → inc = [150] 此时 data = [1] , inc = [150] top(): 返回 data.top() + inc.top() = 1 + 150 = 151 pop(): value = 1 , delta = 150 返回值 = 1 + 150 = 151 栈空，无需传播 通过这种惰性更新机制，所有操作的时间复杂度都是O(1)，符合题目要求。增量操作被延迟到元素被访问时才实际计算，避免了遍历修改的开销。