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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:25 2023-09-13 16:06:25 Updated    

请你设计一个支持对其元素进行增量操作的栈。

实现自定义栈类 CustomStack ：

  • CustomStack(int maxSize)：用 maxSize 初始化对象，maxSize 是栈中最多能容纳的元素数量。
  • 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 stk = new CustomStack(3); // 栈是空的 []
stk.push(1);                          // 栈变为 [1]
stk.push(2);                          // 栈变为 [1, 2]
stk.pop();                            // 返回 2 --> 返回栈顶值 2，栈变为 [1]
stk.push(2);                          // 栈变为 [1, 2]
stk.push(3);                          // 栈变为 [1, 2, 3]
stk.push(4);                          // 栈仍然是 [1, 2, 3]，不能添加其他元素使栈大小变为 4
stk.increment(5, 100);                // 栈变为 [101, 102, 103]
stk.increment(2, 100);                // 栈变为 [201, 202, 103]
stk.pop();                            // 返回 103 --> 返回栈顶值 103，栈变为 [201, 202]
stk.pop();                            // 返回 202 --> 返回栈顶值 202，栈变为 [201]
stk.pop();                            // 返回 201 --> 返回栈顶值 201，栈变为 []
stk.pop();                            // 返回 -1 --> 栈为空，返回 -1

提示：

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

分析

可以发现题目要求我们实现的 push、pop 和 inc 三个功能中，前两个功能就是普通的栈所具有的功能，为什么普通的栈没有 inc 功能呢？因为普通的栈只有栈顶元素是「可见」的，所以要实现的这个功能，我们就要让栈中的所有元素「可见」。

方法一：模拟

我们使用数组模拟栈，用一个变量 top 来记录当前栈顶的位置。

  • 对于 push 操作，首先判断当前元素的个数是否达到上限，如果没有达到，就把 top 后移一个位置并添加一个元素。

  • 对于 pop 操作，首先判断当前栈是否为空，非空返回栈顶元素并将 top 前移一位，否则返回 -1。

  • 对于 inc 操作，直接对栈底的最多 k 个元素加上 val。

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class CustomStack {
public:
    vector<int> stk;
    int top;

    CustomStack(int maxSize) {
        stk.resize(maxSize);
        top = -1;
    }
    
    void push(int x) {
        if (top != stk.size() - 1) {
            ++top;
            stk[top] = x;
        }
    }
    
    int pop() {
        if (top == -1) {
            return -1;
        }
        --top;
        return stk[top + 1];
    }
    
    void increment(int k, int val) {
        int lim = min(k, top + 1);
        for (int i = 0; i < lim; ++i) {
            stk[i] += val;
        }
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class CustomStack {
    int[] stack;
    int top;

    public CustomStack(int maxSize) {
        stack = new int[maxSize];
        top = -1;
    }
    
    public void push(int x) {
        if (top != stack.length - 1) {
            ++top;
            stack[top] = x;
        }
    }
    
    public int pop() {
        if (top == -1) {
            return -1;
        }
        --top;
        return stack[top + 1];
    }
    
    public void increment(int k, int val) {
        int limit = Math.min(k, top + 1);
        for (int i = 0; i < limit; ++i) {
            stack[i] += val;
        }
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class CustomStack:

    def __init__(self, maxSize: int):
        self.stk = [0] * maxSize
        self.top = -1

    def push(self, x: int) -> None:
        if self.top != len(self.stk) - 1:
            self.top += 1
            self.stk[self.top] = x

    def pop(self) -> int:
        if self.top == -1:
            return -1
        self.top -= 1
        return self.stk[self.top + 1]

    def increment(self, k: int, val: int) -> None:
        lim = min(k, self.top + 1)
        for i in range(lim):
            self.stk[i] += val

复杂度分析

  • 时间复杂度：初始化（构造函数）、push 操作和 pop 操作的渐进时间复杂度为 O(1)，inc 操作的渐进时间复杂度为 O(k)。

  • 空间复杂度：这里用到了一个长度为 maxSize 的数组作为辅助空间，渐进空间复杂度为 O({\rm maxSize})。

方法二：模拟优化

在方法一中，只剩下 inc 操作的时间复杂度不为 O(1)，因此可以尝试对该操作进行优化。

我们用一个辅助数组 add 记录每次 inc 操作。具体地，如果 inc 操作是将栈底的 k 个元素（将 k 与栈中元素个数取较小值）增加 val，那么我们将 add[k - 1] 增加 val。这样做的目的在于，只有在 pop 操作时，我们才需要知道栈顶元素的具体值，在其余的情况下，我们只要存储每个元素的增量就行了。

因此在遇到 pop 操作时，我们返回栈顶元素的初始值加上增量 add[top]。在这之后，我们将增量向栈底进行传递，累加至 add[top - 1] 处，这样 inc 操作的时间复杂度也减少至 O(1) 了。

[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class CustomStack {
public:
    vector<int> stk, add;
    int top;

    CustomStack(int maxSize) {
        stk.resize(maxSize);
        add.resize(maxSize);
        top = -1;
    }
    
    void push(int x) {
        if (top != stk.size() - 1) {
            ++top;
            stk[top] = x;
        }
    }
    
    int pop() {
        if (top == -1) {
            return -1;
        }
        int ret = stk[top] + add[top];
        if (top != 0) {
            add[top - 1] += add[top];
        }
        add[top] = 0;
        --top;
        return ret;
    }
    
    void increment(int k, int val) {
        int lim = min(k - 1, top);
        if (lim >= 0) {
            add[lim] += val;
        }
    }
};
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class CustomStack {
    int[] stack;
    int[] add;
    int top;

    public CustomStack(int maxSize) {
        stack = new int[maxSize];
        add = new int[maxSize];
        top = -1;
    }
    
    public void push(int x) {
        if (top != stack.length - 1) {
            ++top;
            stack[top] = x;
        }
    }
    
    public int pop() {
        if (top == -1) {
            return -1;
        }
        int ret = stack[top] + add[top];
        if (top != 0) {
            add[top - 1] += add[top];
        }
        add[top] = 0;
        --top;
        return ret;
    }
    
    public void increment(int k, int val) {
        int limit = Math.min(k - 1, top);
        if (limit >= 0) {
            add[limit] += val;
        }
    }
}
[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class CustomStack:

    def __init__(self, maxSize: int):
        self.stk = [0] * maxSize
        self.add = [0] * maxSize
        self.top = -1

    def push(self, x: int) -> None:
        if self.top != len(self.stk) - 1:
            self.top += 1
            self.stk[self.top] = x

    def pop(self) -> int:
        if self.top == -1:
            return -1
        ret = self.stk[self.top] + self.add[self.top]
        if self.top != 0:
            self.add[self.top - 1] += self.add[self.top]
        self.add[self.top] = 0
        self.top -= 1
        return ret

    def increment(self, k: int, val: int) -> None:
        lim = min(k - 1, self.top)
        if lim >= 0:
            self.add[lim] += val

复杂度分析

  • 时间复杂度：所有操作的渐进时间复杂度均为 O(1)。

  • 空间复杂度：这里用到了两个长度为 maxSize 的数组作为辅助空间，渐进空间复杂度为 O({\rm maxSize})。

 Comments
On this page
1381-设计一个支持增量操作的栈