LeetCode 1381. 设计一个支持增量操作的栈

2026-04-10 HGNULB 约 10 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 1381. 设计一个支持增量操作的栈

题意分析

要求实现一个容量上限为 maxSize 的栈，支持三个操作：push(x) 在未满时压入元素、已满时静默丢弃；pop() 弹出并返回栈顶，空栈返回 $-1$；increment(k, val) 把栈底起最靠下的 $k$ 个元素每个都加上 val，若栈内不足 $k$ 个则全部加。

三个操作里只有 increment 是非平凡的。它作用的对象是「栈底方向的一段前缀」，而 pop 只从栈顶方向取元素——修改端和读取端在栈的两头，这个错位就是本题的全部设计空间。

约束给出的信号很直接：三种操作的调用总次数不超过 $1000$，maxSize 也不超过 $1000$。$10^6$ 的暴力量级其实能过，但题目把 increment 单列出来当作卖点，面试官期待的显然是把 $O(k)$ 的批量加法摊到出栈时结算，做到三个操作全 $O(1)$。答不出这个就等于没答。

边界要盯住四处：栈满时 push 必须无声返回而不是抛异常或覆盖；空栈 pop 返回 $-1$；increment 的 $k$ 可能大于当前元素数量，要截断；$k$ 也可能是 $0$，此时什么都不做。

解法：栈 + 延迟增量数组

核心思路

暴力做法是用数组当栈，increment(k, val) 时循环前 $\min(k, size)$ 个位置逐个加 val。瓶颈在于同一个元素可能被反复加：连续 $m$ 次 increment(1000, 1) 要做 $10^6$ 次加法，而这些加法的结果直到那个元素被 pop 出来才真正被观察到。

关键观察是：元素的值只在 pop 的那一刻才需要是正确的。中间过程谁也看不见。既然如此，就不必立刻把增量摊到每个元素身上，只要在出栈时能把「这个元素一共欠了多少」算出来即可。

于是引入一个与栈等长的辅助数组 inc，它的语义是本解法的核心定义：inc[i] 表示「栈底到下标 $i$ 的这整段前缀」还各欠一次 inc[i] 的加值。注意它是打在区间右端点上的标记，而不是每个元素各自的欠账。increment(k, val) 因此只需一次写入——把 val 累加到 inc[min(k, size) - 1] 上，$O(1)$ 完成。

由此得到贯穿始终的不变量：下标 $i$ 处元素的真实值等于 stack[i] + inc[i] + inc[i+1] + ... + inc[size-1]，即它自身及其之上所有标记的后缀和。栈顶下标 size - 1 是特例——它上面没有别的标记，真实值就是 stack[size-1] + inc[size-1]，可以 $O(1)$ 直接取出。

pop 正是利用这个特例：先按 stack[idx] + inc[idx] 结算栈顶，然后必须把 inc[idx] 下推给新的栈顶 inc[idx-1]。因为 inc[idx] 这个标记覆盖的是 $[0, idx]$ 整段，元素 idx 走了，标记对剩下的 $[0, idx-1]$ 依然有效，把它并入 inc[idx-1] 就恰好保持了不变量。这一步是整个设计的枢纽，漏掉它下方元素的增量就凭空蒸发。

解题步骤

构造函数开两个长度为 maxSize 的数组 stack 和 inc，并置 size = 0。用定长数组而不是动态容器，是因为容量上限已知，且 inc 必须与栈位置一一对应；inc 全为 $0$ 表示没有任何欠账。

push(x)：若 size == maxSize 直接 return，题目明确要求满栈丢弃；否则 stack[size++] = x。这里不需要给 inc[size] 清零，因为该槽位上一次被 pop 时已经归零了（见下一条），这个清零责任的归属要固定，否则会出现脏数据。

pop()：空栈返回 $-1$；否则取 idx = size - 1，答案为 stack[idx] + inc[idx]，把栈顶自身的欠账当场结清。

pop() 中把 inc[idx] 下推：if (idx > 0) inc[idx - 1] += inc[idx];。这是维持不变量的关键一步——标记覆盖的是前缀而非单点，元素出栈后标记要留给新的栈顶继承。idx == 0 时下面已经没有元素，标记随之作废。

pop() 中把 inc[idx] 置 $0$ 再 size--。归零是为了让这个槽位下次被 push 复用时是干净的，把清零责任放在 pop 而不是 push，两处只能选一处，选定后不能摇摆。

increment(k, val)：算出 idx = min(k, size) - 1，若 idx >= 0 则 inc[idx] += val。取 min 是因为 $k$ 可能超过实际元素数；减一是把「前 $k$ 个」转成「右端点下标」；idx < 0 对应 $k = 0$ 或空栈，什么都不做。注意是 += 而不是 =，多次 increment 落在同一右端点时要叠加。

以 CustomStack(3) 走一遍 push(1) → push(2) → increment(2, 100) → increment(1, 100) → pop() → pop() → pop()：

push(1)：stack = [1, _, _]，inc = [0, 0, 0]，size = 1。
push(2)：stack = [1, 2, _]，size = 2。
increment(2, 100)：idx = min(2, 2) - 1 = 1，inc = [0, 100, 0]。语义是「$[0,1]$ 这两个元素各欠 100」。
increment(1, 100)：idx = min(1, 2) - 1 = 0，inc = [100, 100, 0]。语义是「$[0,0]$ 再欠 100」，所以元素 0 共欠 200、元素 1 共欠 100。
pop()：idx = 1，返回 stack[1] + inc[1] = 2 + 100 = 102。下推 inc[0] += inc[1] 得 inc = [200, 0, 0]，再置 inc[1] = 0（已是 0），size = 1。此刻元素 0 的欠账 200 完整保留。
pop()：idx = 0，返回 stack[0] + inc[0] = 1 + 200 = 201。idx == 0 不下推，置 inc[0] = 0，size = 0。
pop()：空栈，返回 $-1$。

输出序列 102, 201, -1，与逐个加值的暴力结果一致。若第一次 pop 忘了下推，inc[0] 停在 100，第二次 pop 会错答成 $101$——那 100 正是第一次 increment 本该留给元素 0 的那份。

代码实现

class CustomStack {
    private final int[] stack;

    private final int[] inc;
    private int size;

    public CustomStack(int maxSize) {
        stack = new int[maxSize];
        inc = new int[maxSize];
        size = 0;
    }

    public void push(int x) {
        if (size == stack.length) {
            return;
        }
        stack[size++] = x;
    }

    public int pop() {
        if (size == 0) {
            return -1;
        }

        int idx = size - 1;
        int answer = stack[idx] + inc[idx];

        if (idx > 0) {
            inc[idx - 1] += inc[idx];
        }
        inc[idx] = 0;
        size--;
        return answer;
    }

    public void increment(int k, int val) {
        int idx = Math.min(k, size) - 1;
        if (idx >= 0) {
            inc[idx] += val;
        }
    }
}

type CustomStack struct {
    stack []int
    inc   []int
    size  int
}

func Constructor(maxSize int) CustomStack {
    return CustomStack{
        stack: make([]int, maxSize),
        inc:   make([]int, maxSize),
        size:  0,
    }
}

func (cs *CustomStack) Push(x int) {
    if cs.size == len(cs.stack) {
        return
    }
    cs.stack[cs.size] = x
    cs.size++
}

func (cs *CustomStack) Pop() int {
    if cs.size == 0 {
        return -1
    }

    idx := cs.size - 1
    answer := cs.stack[idx] + cs.inc[idx]

    if idx > 0 {
        cs.inc[idx-1] += cs.inc[idx]
    }
    cs.inc[idx] = 0
    cs.size--
    return answer
}

func (cs *CustomStack) Increment(k int, val int) {
    idx := k
    if idx > cs.size {
        idx = cs.size
    }
    idx--
    if idx >= 0 {
        cs.inc[idx] += val
    }
}

复杂度分析

时间复杂度：三个操作均为 $O(1)$。push 是一次数组写入；pop 是一次读、一次加法、一次下推、一次归零；increment 是一次取最小值和一次累加。构造函数为 $O(maxSize)$，用于分配并清零两个数组。

空间复杂度：$O(maxSize)$。stack 与 inc 各占一份定长空间，与实际压入的元素个数无关，只取决于声明的容量上限。

关键点总结

懒惰求值的通用套路：当中间状态外部不可见时，把批量修改压缩成一个标记，推迟到读取的那一刻再结算。这条原则在线段树的懒标记、差分数组、并查集路径压缩里反复出现。

标记的语义必须一次性定死并写在注释里。本题 inc[i] 是「$[0, i]$ 整段的欠账」而非「元素 $i$ 自己的欠账」，两种定义会导出完全不同的下推逻辑，中途混用必错。

修改端与读取端错位时，找那个「唯一能 $O(1)$ 求值的位置」。这里栈顶恰好没有更上层的标记压着，于是 pop 能直接结算，而下推保证了下一个栈顶继续享有这个性质。

责任归属要单点化：inc 槽位的清零只在 pop 里做，push 不再重复清零。任何一份状态由谁维护，设计题里必须唯一。

面试视角：面试官几乎必问「不用 inc 数组直接循环加行不行」。要主动给出复杂度对比——暴力是 increment $O(k)$、其余 $O(1)$，本解法三者全 $O(1)$——并说明数据范围虽小但设计题考的就是摊还思想。追问「能不能不下推」时，答「因为标记覆盖前缀区间，元素出栈只是区间右端点左移，标记本身没有失效」。

这是差分思想的栈上变体：inc 存的是区间右端点的增量，pop 时的下推等价于从右向左做后缀累加，与差分数组还原前缀和是同一件事。

易错点总结

pop 时忘记 inc[idx - 1] += inc[idx]：push(1) → push(2) → increment(2, 100) → pop() → pop() 会返回 102, 1，第二个值丢掉了 100 的增量，正确应为 102, 101。

increment 里写 inc[idx] = val 而非 +=：increment(1, 100) 后再 increment(1, 50)，pop 只加 50 而不是 150。

increment 忘记对 size 取 min：栈内只有 2 个元素却调用 increment(5, 1)，idx = 4 直接数组越界；即便不越界，写进 inc[4] 的值也永远不会被结算。

increment 未判 idx >= 0：increment(0, 100) 算出 idx = -1，inc[-1] 在 Java 抛 ArrayIndexOutOfBoundsException，Go 直接 panic。

pop 后不把 inc[idx] 归零：push(1) → increment(1, 100) → pop() → push(5) → pop() 第二次会返回 $105$，那 100 是上一轮的残留欠账，正确应为 $5$。

push 满栈时抛异常或强行覆盖栈顶：CustomStack(1) 上执行 push(1) → push(2) → pop()，覆盖写法会返回 $2$，题目要求返回 $1$。

空栈 pop 返回 $0$ 或访问 stack[-1]：新建栈直接 pop() 应返回 $-1$，返回 $0$ 会与「栈里真的存了 $0$」的合法情况混淆。

把 inc 数组开成 size 长度而非 maxSize：size 是动态的，构造时为 $0$，第一次 increment 就越界。

pop 里先 size-- 再用 idx = size - 1：push(1) → push(2) → pop() 会取到下标 $0$，返回 $1$ 而不是栈顶 $2$。

increment 理解成给栈顶 $k$ 个加值：push(1) → push(2) → increment(1, 100) → pop() 若按栈顶理解会返回 $102$，题目要求加的是栈底方向的第一个元素，正确返回 $2$。

相似题目

题目	难度	考察点
155. 最小栈	中等	同为栈上附加信息，但辅助栈存的是历史最小值快照，不涉及延迟结算
1109. 航班预订统计	中等	差分数组的标准形态，区间加法离线批处理后一次性前缀和还原
370. 区间加法	中等	同样把区间加压成端点标记，但只需最终快照，无需支持中途读取
232. 用栈实现队列	简单	另一种摊还设计：元素在两栈间搬运，均摊 $O(1)$ 而非严格 $O(1)$
622. 设计循环队列	中等	定长数组 + 容量边界判定，考的是下标回绕而非附加状态
380. O(1) 时间插入、删除和获取随机元素	中等	用数组与哈希表互补达成全 $O(1)$，靠尾部交换删除而非延迟标记
1472. 设计浏览器历史记录	中等	同为定长数组模拟栈，难点在前进指针的失效范围而非增量传递
307. 区域和检索 - 数组可修改	中等	单点改 + 区间查，需树状数组或线段树，是懒标记思想的完整版