)
问题解构
力扣第 3629 题是“设计一个支持增量操作的栈”（Design a Stack With Increment Operation）。该问题要求设计一个定长栈，除了支持标准的push和pop操作外，还需要支持一个特殊的increment(k, val)操作，该操作会将栈底的前k个元素（即最早入栈的元素）全部增加val。如果栈中元素少于k个，则将所有元素增加val。
核心难点：increment操作如果直接遍历栈底的前k个元素进行加法，时间复杂度为 O(k)，在最坏情况下（k 等于栈容量）可能达到 O(n)，导致多次操作后整体性能下降。因此，需要设计一种高效的数据结构，使得push、pop和increment操作的时间复杂度均为O(1)。
方案推演
为了实现 O(1) 时间复杂度的increment操作，可以采用“惰性增量”（Lazy Increment）或“差分数组”（Difference Array）的思想。具体方案如下：
数据结构设计：
- 使用一个数组
stack存储栈中的元素。 - 使用另一个数组
inc作为增量数组，inc[i]表示从栈底到位置i（含）的所有元素需要累加的增量值。 - 维护一个整数
top表示栈顶指针（指向下一个可插入位置）。
- 使用一个数组
操作实现：
push(x)：如果栈未满，将x存入stack[top]，并将inc[top]初始化为 0，然后top++。pop()：如果栈为空，返回 -1。否则，top--。由于inc[top]可能包含了从栈底到该位置的累积增量，因此实际弹出的值应为stack[top] + inc[top]。此外，为了将增量传递给更靠近栈顶的元素（如果存在），需要将inc[top-1]加上inc[top]（即增量上浮），然后将inc[top]重置为 0。increment(k, val)：该操作只需更新增量数组。具体地，将inc[min(k-1, top-1)]增加val。因为inc[i]表示从栈底到i的累积增量，所以只需在边界处增加val，后续在pop时通过上浮传递增量。
时间复杂度分析：
push：O(1)。pop：O(1)。increment：O(1)。
具体实现
以下是基于上述方案的 Java 代码实现，包含详细注释。
class CustomStack { private int[] stack; // 存储栈元素 private int[] inc; // 增量数组，inc[i] 表示从栈底到 i 位置的累积增量 private int top; // 栈顶指针，指向下一个可插入位置 private int maxSize; // 栈的最大容量 public CustomStack(int maxSize) { this.maxSize = maxSize; stack = new int[maxSize]; inc = new int[maxSize]; top = 0; // 栈初始为空 } public void push(int x) { if (top >= maxSize) { return; // 栈已满，按题目要求不执行任何操作 } stack[top] = x; inc[top] = 0; // 新元素初始增量为 0 top++; } public int pop() { if (top == 0) { return -1; // 栈为空 } top--; int res = stack[top] + inc[top]; // 实际值为元素值加上累积增量 if (top > 0) { inc[top - 1] += inc[top]; // 将增量传递给前一个元素（上浮） } inc[top] = 0; // 重置当前位的增量 return res; } public void increment(int k, int val) { if (top == 0) { return; // 栈为空，无需操作 } int idx = Math.min(k, top) - 1; // 确定需要增加增量的边界位置 inc[idx] += val; // 在边界处增加增量 } }示例与解释
假设栈容量为 5，依次执行以下操作：
push(1)→ 栈: [1]push(2)→ 栈: [1, 2]increment(2, 100)→ 栈底前 2 个元素各增加 100，但实际只更新inc[1] = 100。push(3)→ 栈: [1, 2, 3]pop()→ 弹出 3（实际值 3 + 0），栈: [1, 2]pop()→ 弹出 2，此时inc[1] = 100上浮到inc[0]，实际值 2 + 100 = 102，栈: [1]pop()→ 弹出 1，实际值 1 + 100 = 101，栈空。
关键点：
increment操作只更新增量数组，不直接修改栈元素，实现了 O(1) 时间复杂度。pop时通过增量上浮（inc[top-1] += inc[top]）确保增量正确传递。- 当栈元素少于
k个时，Math.min(k, top)确保不会越界。
复杂度分析
- 时间复杂度：
push、pop、increment均为 O(1)。 - 空间复杂度：O(n)，其中 n 为栈的最大容量，用于存储栈数组和增量数组。
应用场景
这种“惰性增量”技巧适用于需要频繁批量更新前缀或子数组的场景，例如：
- 数据库中的批量更新操作。
- 游戏开发中的伤害区域效果（对范围内所有单位增加效果）。
- 实时数据分析中的滑动窗口统计。
通过延迟计算增量，将本应 O(k) 的操作优化为 O(1)，显著提升了性能，尤其在大数据量或高频操作场景下优势明显。
