【Day 3】 设计一个支持增量操作的栈

题目描述

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

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


示例：

输入：
["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


提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/design-a-stack-with-increment-operation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的回答

https://github.com/leetcode-pp/91alg-1/issues/18#issuecomment-637899087

解法一

时空复杂度

O(n)

/**
 * @param {number} maxSize
 */
var CustomStack = function(maxSize) {
  this.max_size = maxSize;
  this.s = [];
};

/**
 * @param {number} x
 * @return {void}
 */
CustomStack.prototype.push = function(x) {
  if (this.s.length < this.max_size) this.s.push(x);
  return this.s;
};

/**
 * @return {number}
 */
CustomStack.prototype.pop = function() {
  if (this.s.length == 0) return -1;
  return this.s.pop();
};

/**
 * @param {number} k
 * @param {number} val
 * @return {void}
 */
CustomStack.prototype.increment = function(k, val) {
  let min = Math.min(k, this.s.length);
  for (i = 0; i < min; i++) {
    this.s[i] += val;
  }
  return this.s;
};

优化

//使用另外一个数组来记录increment，Lazy increment，只有在数被pop的时候才去increment 数组里找到该数所需要加上的数，实现O(1)
CustomStack.prototype.increment = function(k, val) {
  let i = Math.min(k, this.s.length) - 1;
  for (let j = 0; j < i; j++) {
    inc[j] = inc[j] ? inc[j] + val : val;
  }
};

参考回答

increment 时间复杂度为 $O(k)$ 的方法

思路

首先我们来看一种非常符合直觉的方法，然而这种方法并不好，increment 操作需要的时间复杂度为 $O(k)$。

push和 pop 就是普通的栈操作。 唯一要注意的是边界条件，这个已经在题目中指明了，具体来说就是：

• push 的时候要判断是否满了
• pop 的时候要判断是否空了

而做到上面两点，只需要一个 cnt 变量记录栈的当前长度，一个 size 变量记录最大容量，并在 pop 和 push 的时候更新 cnt 即可。

代码

class CustomStack:

    def __init__(self, size: int):
        self.st = []
        self.cnt = 0
        self.size = size

    def push(self, x: int) -> None:
        if self.cnt < self.size:
            self.st.append(x)
            self.cnt += 1


    def pop(self) -> int:
        if self.cnt == 0: return -1
        self.cnt -= 1
        return self.st.pop()


    def increment(self, k: int, val: int) -> None:
        for i in range(0, min(self.cnt, k)):
            self.st[i] += val

复杂度分析

• 时间复杂度：push 和 pop 操作的时间复杂度为 $O(1)$（讲义有提到），而 increment 操作的时间复杂度为 $O(min(k, cnt))$
• 空间复杂度：$O(1)$

increment 时间复杂度为 $O(1)$ 的方法

思路

和上面的思路类似，不过我们采用空间换时间的方式。采用一个额外的数组 incrementals 来记录每次 incremental 操作。

具体算法如下：

• 初始化一个大小为 maxSize 的数组， 并全部填充 0
• push 操作不变，和上面一样
• increment 的时候，我们将 incremental 信息，如何记录呢？我这里画了一个图

如图黄色部分是我们需要执行增加操作，我这里画了一个挡板分割，实际上这个挡板不存在。那么如何记录黄色部分的信息呢？我举个例子来说

比如：

• 调用了 increment(3, 2)，就把 increment[3] 增加 2。
• 继续调用 increment(2, 5)，就把 increment[2] 增加 5。

而当我们 pop 的时候：

• 只需要将栈顶元素加上 increment[cnt - 1] 即可， 其中 cnt 为栈当前的大小。
• 另外，我们需要将 increment[cnt - 1] 更新到 increment[cnt - 2]，并将 increment[cnt - 1] 重置为 0。

代码

class CustomStack:

    def __init__(self, size: int):
        self.st = []
        self.cnt = 0
        self.size = size
        self.incrementals = [0] * size

    def push(self, x: int) -> None:
        if self.cnt < self.size:
            self.st.append(x)
            self.cnt += 1


    def pop(self) -> int:
        if self.cnt == 0: return -1
        if self.cnt >= 2:
            self.incrementals[self.cnt - 2] += self.incrementals[self.cnt - 1]
        ans = self.st.pop() + self.incrementals[self.cnt - 1]
        self.incrementals[self.cnt - 1] = 0
        self.cnt -= 1
        return ans


    def increment(self, k: int, val: int) -> None:
            if self.cnt:
                self.incrementals[min(self.cnt, k) - 1] += val

复杂度分析

• 时间复杂度：全部都是 $O(1)$
• 空间复杂度：我们维护了一个大小为 maxSize 的数组，因此平均到每次的空间复杂度为 $O(maxSize / N)$，其中 N 为操作数。

优化的 increment 时间复杂度为 $O(1)$ 的方法

思路

上面的思路无论如何，我们都需要维护一个大小为 $O(maxSize)$ 的数组 incremental 。而这实际上可以稍微优化一点。

代码

class CustomStack:

    def __init__(self, size: int):
        self.st = []
        self.cnt = 0
        self.size = size
        self.incrementals = []

    def push(self, x: int) -> None:
        if self.cnt < self.size:
            self.st.append(x)
            self.incrementals.append(0)
            self.cnt += 1


    def pop(self) -> int:
        if self.cnt == 0: return -1
        self.cnt -= 1
        if self.cnt >= 1:
            self.incrementals[-2] += self.incrementals[-1]
        return self.st.pop() + self.incrementals.pop()


    def increment(self, k: int, val: int) -> None:
        if self.incrementals:
            self.incrementals[min(self.cnt, k) - 1] += val

复杂度分析

• 时间复杂度：全部都是 O(1)
• 空间复杂度：我们维护了一个大小为 cnt 的数组，因此平均到每次的空间复杂度为 $O(cnt / N)$，其中 N 为操作数，cnt 为操作过程中的栈的最大长度（小于等于 maxSize）。

可以看出优化的解法在 maxSize 非常大的时候是很有意义的。

相关题目

• 155. 最小栈 (opens new window)