What is the main idea behind this stack problem?

The problem focuses on managing a stack with push, pop, and bottom-element increment operations efficiently using array-based state management.

How can increment be optimized in this problem?

By tracking pending increments in a separate array and applying them lazily on pop, each increment operation can be done in O(1) time.

What happens if I pop from an empty stack?

You should return -1 whenever pop is called on an empty stack, maintaining consistency with the problem's requirements.

How does maxSize affect push operations?

Push operations must check the current stack size and only add elements if the stack has not reached maxSize to avoid overflow.

Does this problem follow a common pattern?

Yes, it follows a stack-based state management pattern where auxiliary structures track extra state like increments for efficiency.

#1381

Medium

auto_awesome栈·状态

LeetCode 题解工作台

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

请你设计一个支持对其元素进行增量操作的栈。实现自定义栈类 CustomStack ： CustomStack(int maxSize) ：用 maxSize 初始化对象， maxSize 是栈中最多能容纳的元素数量。 void push(int x) ：如果栈还未增长到 maxSize ，就将 x…

数组栈设计

题目描述

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

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

lightbulb

解题思路

方法一：数组模拟

我们可以用一个数组 $stk$ 来模拟栈，用一个整数 $i$ 表示下一个入栈的元素位置。另外，我们还需要一个数组 $add$ 来记录每个位置上的增量累加值。

调用 $push(x)$ 时，如果 $i \lt maxSize$ ，我们将 $x$ 放入 $stk[i]$ 中，并将 $i$ 加一。

调用 $pop()$ 时，如果 $i \leq 0$ ，说明栈为空，返回 $-1$ 。否则我们将 $i$ 减一，答案为 $stk[i] + add[i]$ ，然后我们将 $add[i - 1]$ 加上 $add[i]$ ，并将 $add[i]$ 清零。最后返回答案。

调用 $increment(k, val)$ 时，如果 $i \gt 0$ ，我们将 $add[\min(i, k) - 1]$ 加上 $val$ 。

时间复杂度 $O(1)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是栈的最大容量。

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

class CustomStack:
    def __init__(self, maxSize: int):
        self.stk = [0] * maxSize
        self.add = [0] * maxSize
        self.i = 0

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

    def pop(self) -> int:
        if self.i <= 0:
            return -1
        self.i -= 1
        ans = self.stk[self.i] + self.add[self.i]
        if self.i > 0:
            self.add[self.i - 1] += self.add[self.i]
        self.add[self.i] = 0
        return ans

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


# Your CustomStack object will be instantiated and called as such:
# obj = CustomStack(maxSize)
# obj.push(x)
# param_2 = obj.pop()
# obj.increment(k,val)

speed

复杂度分析

指标	值
时间	O(1)
空间	O(\text{maxSize})

psychology

面试官常问的追问

外企场景

question_mark
Checking if you optimize increment to avoid O(n) per operation.
question_mark
Expecting proper handling of maxSize and empty stack cases.
question_mark
Looking for clear separation of array state and increment tracking to ensure correctness.

warning

常见陷阱

外企场景

error
Applying increment directly on all k elements causes O(n) time per increment.
error
Forgetting to check stack size before push, causing overflow.
error
Returning wrong value on pop when stack is empty instead of -1.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Implement the stack without using extra increment array but with higher increment time complexity.
arrow_right_alt
Allow decrement operations for the bottom k elements instead of increment.
arrow_right_alt
Support dynamic resizing of the stack beyond a fixed maxSize while keeping increment efficient.

help

常见问题

外企场景

继续练习

#1472 设计浏览器历史记录 #1357 每隔 n 个顾客打折 #1352 最后 K 个数的乘积