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

2026-04-10 HGNULB 约 5 分钟

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

分类

LeetCode CodeTop 中等未解决 2-5 字节

题目描述

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

题意分析

实现容量为 maxSize 的栈：未满时允许入栈，已满则忽略；弹出栈顶并返回其当前值，空栈返回 -1。increment(k, val) 将底部前 k 个元素都增加 val，不足 k 个时增加当前全部元素。

解法：栈 + 延迟增量数组

核心思路

[!blue]

增量总是作用于从栈底开始的前缀，而元素只会从栈顶弹出。可以暂不逐个改值，只在被增加前缀的最高位置记一个标记，等弹出时再向下传递，让每次操作都只修改常数个位置。

stack[i] 保存入栈时的值，size 表示当前元素个数。inc[j] 表示整个前缀 [0, j] 尚需增加的量，因此位置 i 的真实值是 stack[i] + inc[i] + ... + inc[size - 1]。标记位于它上方或自身时才覆盖它，位于下方的标记不会影响它。

执行 increment 时，实际覆盖数量为 min(k, size)，只需在其最后一个下标处累加 val。根据真实值公式，这恰好让覆盖前缀中的每个元素都增加一次，前缀外的元素不变；多次操作直接叠加标记即可。

弹出时，栈顶上方没有标记，其真实值就是 stack[idx] + inc[idx]。但 inc[idx] 仍应作用于底下所有元素，所以将它加到 inc[idx - 1]，保留剩余元素真实值公式中的同一份增量。之后清零旧槽位、减少 size；如果原来只有一个元素，就没有向下传递的对象。

入栈只需写入新槽位。未使用的增量槽位初始为 0，复用的槽位也已在弹出时清零；下方旧标记只覆盖旧前缀，因此新元素不会继承入栈之前的增量。栈满、栈空和空增量前缀分别提前处理即可。

解题步骤

increment 在 min(k,size)−1 处累加标记。

pop 读取栈顶原值加标记，向下传播后清空槽位。

push 未满时写入，满栈忽略。

代码实现

class CustomStack {
    private final int[] stack;

    // inc[i] 是底部到位置 i 的整个前缀仍需增加的值。
    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[i] 是底部到位置 i 的整个前缀仍需增加的值。
    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(C)$，push、pop、increment 均为最坏 $O(1)$，C 为容量。

空间复杂度：$O(C)$，值数组与增量数组。

关键点总结

[!green]

标记覆盖前缀，不是只增加标记所在的单点。

空栈或覆盖数量零时不写负下标。

易错点总结

[!yellow]

弹出不下传会丢掉底部元素应有的增量。

多次 increment 使用覆盖赋值会丢失旧增量。

槽位不清零，后来压入的元素会继承过期值。

相似题目

题目	难度	关联与区别
370. 区间加法	中等	同样延迟应用区间增量，本题在栈中把底部范围增量记录到边界，并在弹栈时向下传递。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/59237989

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！