【Leetcode】1381. Design a Stack With Increment Operation

题目地址：

https://leetcode.com/problems/design-a-stack-with-increment-operation/

要求设计一个栈，可以实现：
1、其容量为一个给定值。如果某个操作使得容量超过上限，则忽略此次操作。
2、void push(int x)：加入一个数$x$，如果超过上限则忽略；
3、int pop()：如果栈空则返回$-1$，否则返回栈顶；
4、void inc(int k, int x)：将从栈底开始的$k$个数，每个数都加上$x$。如果不足$k$个，则栈中所有数都加上$x$。

可以使用懒标记。开两个向量$s$和$a$，$s$表示栈本身，$a$存储的是加数懒标记，即$a[i]$表示：$s[i]$中的数，如果不考虑$a[i+1:]$的话，应该加上$a[i]$才是真实值。push的时候，直接将$x$加进$s$，将$0$加入$a$；inc的时候，将$a[k-1]$加上$x$，表示$s[0:k-1]$应该整体加上$x$，但是还没有加，只是懒标记。在pop的时候，如果当前有$n$个元素，则要执行a[n - 2] += a[n - 1]，表示$s[n-2]$要补加上$a[n-1]$，然后再返回$s[n-1]+a[n-1]$，并pop两个向量。代码如下：

class CustomStack {
 public:
  vector<int> stk, add;
  int cap;
  CustomStack(int maxSize) { cap = maxSize; }

  void push(int x) {
    if (stk.size() == cap) return;
    stk.push_back(x);
    add.push_back(0);
  }

  int pop() {
    if (stk.empty()) return -1;
    int n = stk.size(), res = stk[n - 1] + add[n - 1];
    if (n >= 2) add[n - 2] += add[n - 1];
    stk.pop_back();
    add.pop_back();
    return res;
  }

  void increment(int k, int val) {
    if (stk.empty()) return;
    k = min(k, (int)stk.size());
    add[k - 1] += val;
  }
};
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

所有操作时间复杂度$O(1)$，空间$O(n)$，$n$为栈中元素个数。