操作序列：
push(1); push(2); push(3); 
increment(2, 100); 
pop(); 
push(4); 
increment(3, 50); 
pop(); pop(); pop();

哈希算法题目：设计一个支持增量操作的栈 题目描述 设计一个栈，除了常规的 push 和 pop 操作外，还需要支持一个增量操作 increment(k, val) ，该操作会将栈底开始的 k 个元素（或栈中所有元素，如果元素数量小于 k ）的值增加 val 。要求所有操作的时间复杂度均为 O(1)。 示例 栈初始为 [] 。 push(1) → 栈: [ 1 ] push(2) → 栈: [ 1, 2 ] push(3) → 栈: [ 1, 2, 3 ] increment(2, 100) → 栈底2个元素（1和2）加100 → 栈: [ 101, 102, 3 ] pop() → 返回3，栈变为 [ 101, 102 ] push(4) → 栈: [ 101, 102, 4 ] increment(3, 50) → 栈底3个元素加50 → 栈: [ 151, 152, 54 ] 连续 pop() 返回 54、152、151。 解题过程 核心思路分析 常规栈的 push 和 pop 是 O(1) 操作，但 increment(k, val) 若直接修改栈底 k 个元素需 O(k) 时间。为达到 O(1) 复杂度，需将增量操作“延迟”到 pop 时再应用。具体方法是用一个辅助栈（或数组）记录增量值。 步骤详解 数据结构设计 使用两个栈： stack ：存储实际元素值。 inc ：记录增量信息， inc[i] 表示从栈底到位置 i（含）的所有元素需累加的增量值。 变量 size 记录当前栈中元素个数。 push 操作 将新元素压入 stack 。 在 inc 中对应位置压入 0（表示新元素尚未被增量操作覆盖）。 increment 操作 若栈非空，将增量 val 累加到 inc[min(k, size) - 1] 位置（即栈底第 k 个元素对应的增量记录点）。 例如， k=2 时，增量应作用于栈底2个元素，将 val 加到 inc[1] （索引从0开始）。这样，当未来弹出栈顶时，增量会通过累加机制传递到下方元素。 pop 操作 若栈空则返回异常。 弹出 stack 顶元素 top 和 inc 顶元素 incTop 。 关键步骤 ：若 inc 非空，将 incTop 值向下传递：将 inc[size-2] （新栈顶对应的增量记录）增加 incTop 。 返回 top + incTop （当前元素值加上累计增量）。 时间复杂度 所有操作均只需常数次栈操作，时间复杂度 O(1)。 示例逐步模拟 初始： stack = [], inc = [], size = 0 push(1) → stack = [1], inc = [0], size=1 push(2) → stack = [1,2], inc = [0,0], size=2 push(3) → stack = [1,2,3], inc = [0,0,0], size=3 increment(2,100) → k=2，修改 inc[1] += 100 → inc = [0,100,0] pop() → 弹出 stack.top()=3 , inc.top()=0 。 向下传递增量： inc[1] += 0 （无变化）。 返回 3+0=3 ， stack = [1,2], inc = [0,100], size=2 push(4) → stack = [1,2,4], inc = [0,100,0], size=3 increment(3,50) → k=3，修改 inc[2] += 50 → inc = [0,100,50] pop() → 弹出 stack.top()=4 , inc.top()=50 。 向下传递： inc[1] += 50 → inc = [0,150,50] （实际 inc 长度已减1，变为 [0,150] ）。 返回 4+50=54 ， stack = [1,2], inc = [0,150] pop() → 弹出 stack.top()=2 , inc.top()=150 。 向下传递： inc[0] += 150 → inc = [150,150] （实际变为 [150] ）。 返回 2+150=152 ， stack = [1], inc = [150] pop() → 弹出 stack.top()=1 , inc.top()=150 。 无元素可传递增量。 返回 1+150=151 ， stack = [], inc = [] 结果与预期一致。