力扣1381-设计一个支持增量操作的栈

摘要: 设计题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

本文看一道设计题，第 180 场周赛 B 题。主要是惰性更新的思想，将修改视为记在账上的贡献。当查询时，再查账把贡献加上去再返回。

$1 题目

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

请你设计一个支持下述操作的栈。

实现自定义栈类 CustomStack ：

• CustomStack(int maxSize)：用 maxSize 初始化对象，maxSize 是栈中最多能容纳的元素数量，栈在增长到 maxSize 之后则不支持 push 操作。
• void push(int x)：如果栈还未增长到 maxSize ，就将 x 添加到栈顶。
• int pop()：弹出栈顶元素，并返回栈顶的值，或栈为空时返回 -1 。
• void inc(int k, int val)：栈底的 k 个元素的值都增加 val 。如果栈中元素总数小于 k ，则栈中的所有元素都增加 val 。

1 <= maxSize <= 1000
1 <= x <= 1000
1 <= k <= 1000
0 <= val <= 100
每种方法 increment，push 以及 pop 分别最多调用 1000 次

示例：

输入：
[“CustomStack”,”push”,”push”,”pop”,”push”,”push”,”push”,”increment”,”increment”,”pop”,”pop”,”pop”,”pop”]
[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
输出：
[null,null,null,2,null,null,null,null,null,103,202,201,-1]
解释：
CustomStack customStack = new CustomStack(3); // 栈是空的 []
customStack.push(1); // 栈变为 [1]
customStack.push(2); // 栈变为 [1, 2]
customStack.pop(); // 返回 2 —> 返回栈顶值 2，栈变为 [1]
customStack.push(2); // 栈变为 [1, 2]
customStack.push(3); // 栈变为 [1, 2, 3]
customStack.push(4); // 栈仍然是 [1, 2, 3]，不能添加其他元素使栈大小变为 4
customStack.increment(5, 100); // 栈变为 [101, 102, 103]
customStack.increment(2, 100); // 栈变为 [201, 202, 103]
customStack.pop(); // 返回 103 —> 返回栈顶值 103，栈变为 [201, 202]
customStack.pop(); // 返回 202 —> 返回栈顶值 202，栈变为 [201]
customStack.pop(); // 返回 201 —> 返回栈顶值 201，栈变为 []
customStack.pop(); // 返回 -1 —> 栈为空，返回 -1

$2 题解

算法：惰性更新

用动态数组 vector<int> vec 作为容纳栈内数据的容器。维护容器中的元素个数 _size，vec[_size - 1] 为栈顶数据，push 和 pop 这两个需求都是在 vec[_size] 上的访问和修改，都是 O(1) 的。

对于 inc(int k, int val) 这个需求，最朴素的做法是直接在 vec 对应位置上修改，$O(N)$。

如果将某次修改 inc(k, v) 视为对下标 0 ~ k 提供 v 贡献的话，因为出栈的次序一定是下标从大到小的，即 k 位置一定比 k - 1 位置先出站，

所以可以只将该贡献记在下标 k 位置，而 0 ~ k - 1 不做记录。k 位置的数据出栈的时候，再将该贡献传给 k - 1 位置，即某位置出栈时，将贡献往栈底传。

因为修改的区间是 $[0, k]$，因此 k 位置的贡献，$[1, k-1]$ 也一定有，又因为出栈顺序是下标从大到小的，因此 $k - 1$ 位置出栈时，$k$ 位置的贡献一定已经更新到 $k - 1$ 位置了，弹出的值一定是对的。

基于以上思路，可以考虑用一个额外数组 contribute 维护多次的区间修改对各个下标的贡献。

例如，有 m 次修改, 每次修改更新一次对应下标的贡献值($O(1)$)。

inc(k1, v1); // 记录 contribute[k1 - 1] += v1
inc(k2, v2); // 记录 contribute[k2 - 1] += v2
...
inc(km, vm); // 记录 contribute[km - 1] += vm

出栈的时候，将贡献加到原数组的值上输出($O(1)$)，若还未到栈底，则将贡献往栈底传($O(1)$)，然后将该位置的贡献值重置为零($O(1)$)。

每个数据进栈一次，出栈一次，均为 $O(1)$，修改时只记录的一个位置，仍然是 $O(1)$

代码 (C++)

class CustomStack {
public:
    CustomStack(int maxSize) {
        _vec = vector<int>(maxSize);
        _contribute = vector<int>(maxSize);
        _size = 0;
        _capacity = maxSize;
    }

    void push(int x) {
        if(_size == _capacity) return;
        _vec[_size] = x;
        ++_size;
    }

    int pop() {
        if(_size == 0) return -1;
        --_size;
        int res = _vec[_size] + _contribute[_size];
        if(_size != 0)
            _contribute[_size - 1] += _contribute[_size];
        _contribute[_size] = 0;
        return res;
    }

    void increment(int k, int val) {
        int kk = min(k, _size);
        // 0 ~ kk -1
        if(kk > 0)
            _contribute[kk - 1] += val;
    }

private:
    vector<int> _vec;
    vector<int> _contribute;
    int _size;
    int _capacity;
};

---