如何设计一个支持增量操作的栈

旧城等待， 2023-07-17 15:46 4阅读 0赞

点击上方蓝字设为星标![format_png][]

下面开始今天的学习～

![format_png 1][]

### 题目描述 ###

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

实现自定义栈类 `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 。

### 题目解析 ###

题目让你设计一个类似栈的数据结构，这个栈除了基本的 `push` 和 `pop` 功能之外，还需要额外支持一个 “从栈底开始的 k 个元素自增 value” 的功能。

想要 AC 这道题目不难，你可以用一个数组来实现栈，对于 “元素自增” 功能，我们就遍历数组的前 k 个值，让其自增即可。

但是**仔细想想**，这样做下来，“元素自增” 功能的时间复杂度就会是 `O(min(k, n))` 其中 n 是栈中当前元素的总数。

我们知道，栈其实是属线性结构，它的两个原始操作都是 `O(1)` 的时间复杂度，如果我们能够让这个额外功能也具有 `O(1)` 的时间复杂度那就再好不过了。

那该如何去思考这个问题呢？

如果不能一次性自增对应的元素，那我们唯一能做的就是保存这个 “元素自增” 操作对应的数据，以备后用。

这里哪些数据是我们必须看重的？

其实就是两个，k 和 value，我们需要知道当前自增操作覆盖栈中的哪些元素。

这里有一点特别重要，**就是我们只需要记录最高位置，因为最高位置往下其实都生效**。

到了这个位置，以后每次 stack 做 `pop` 操作都需要加上 value。当然，如果在这个时候，往 stack 中进行 `push` 操作，之前的 value 是不会对 `push` 进来的新值生效的。

于是基于这两点，我们可以创建一个数组，这个数组专门记录奏效的最高位置，然后这个位置过了之后，就将对应的值清零，并将值移加到下一个位置。

在这之中，有一个重点就是，生效的元素在任何时候都不能大于栈中现存的元素。

这样下来，我们可以把时间复杂度降到 `O(1)`，符合我们的预期。

### 参考代码 ###

class CustomStack {
        private Stack<Integer> stack;
        private int[] inc;
        private int maxSize;
    
        public CustomStack(int maxSize) {
            this.maxSize = maxSize;
            this.inc = new int[maxSize];
            this.stack = new Stack<>();
        }
    
        public void push(int x) {
            if (stack.size() == maxSize) {
                return;
            }
    
            stack.add(x);
        }
    
        public int pop() {
            int index = stack.size() - 1;
            if (index < 0) {
                return -1;
            }
    
            int result = inc[index] + stack.pop();
    
            // 对高位生效的 value，也同样对低位生效
            // 将高位的值移加到低位
            if (index > 0) {
                inc[index - 1] += inc[index];
            }
    
            // 高位的值清零
            inc[index] = 0;
    
            return result;
        }
    
        public void increment(int k, int val) {
            // 栈为空，自增操作不会对任何元素生效，退出
            if (stack.isEmpty()) {
                return;
            }
    
            // 必须保证生效的值不超过当前存在的元素的个数范围
            int index = Math.min(k, stack.size()) - 1;
    
            // 记录最高值
            inc[index] += val;
        }
    }

**END**

--------------------

![format_png 2][]

● [答应我，别再if/else走天下了可以吗][if_else]

[● ][Link 1][如何利用寒假的时间来准备2020年的蓝桥杯?][2020]

● [给大家推荐一款软件][Link 2]

● [关于计算机读研的小建议][Link 3]

![format_png 3][]

点“在看”你懂得

![format_png 4][]

[format_png]: /images/20230528/473cab1e4905464194fa4c926712fe4d.png
[format_png 1]: /images/20230528/0a8e32f5a5044382b8a5074eea2f49ae.png
[format_png 2]: /images/20230528/eafdc95568b04994920c74e76b18c93e.png
[if_else]: https://blog.csdn.net/kexuanxiu1163/article/details/104140332
[Link 1]: http://mp.weixin.qq.com/s?__biz=Mzg2MzE5MjMxNQ%3D%3D&chksm=ce7ef418f9097d0e01bfe9410a9e40e9f4337c835c87e28332e6a8d8fd8b91b4794164f4c1a1&idx=1&mid=2247491980&scene=21&sn=5ef03c0108a5730fa28e492ec77e22d9#wechat_redirect
[2020]: https://blog.csdn.net/kexuanxiu1163/article/details/104140333
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e6038cd79e92ec7f54e62aaf535c402eed0be07e97d1fdbced663280d2dccdda047ee099c&idx=1&mid=2247487417&scene=21&sn=13d97404f7f5700bb901171e4d9f91e4#wechat_redirect
[Link 3]: https://blog.csdn.net/kexuanxiu1163/article/details/104078939
[format_png 3]: /images/20230528/f6a1714d6b4b4ed9b3c82c465c03e7a8.png
[format_png 4]: /images/20230528/e94c401061ca487a8c705abfc7b7e01d.png