LeetCode 1381. Design a Stack With Increment Operation

Question

Design a stack which supports the following operations.

Implement the CustomStack class:

  • CustomStack(int maxSize) Initializes the object with maxSize which is the maximum number of elements in the stack or do nothing if the stack reached the maxSize.
  • void push(int x) Adds x to the top of the stack if the stack hasn’t reached the maxSize.
  • int pop() Pops and returns the top of stack or -1 if the stack is empty.
  • void inc(int k, int val) Increments the bottom k elements of the stack by val. If there are less than k elements in the stack, just increment all the elements in the stack.

Constraints:

  • 1 <= maxSize <= 1000
  • 1 <= x <= 1000
  • 1 <= k <= 1000
  • 0 <= val <= 100
  • At most 1000 calls will be made to each method of increment, push and pop each separately.

Solution

inc操作是这个题的重点,如果采取常用的栈操作,需要弹出再放入,降低其时间复杂度。

  • Solution1: 在比赛中,我看见如上的参数限制,所以我想到使用基于数组的栈,这样在进行inc,只需要从头开始加。
  • Solution2: 参考了Lee215大佬的解法后发现,思路更加妙。依然采取栈,但是需要一个数组来记录每次加的数,并且放在最高位,每次需要pop的时候, 就依次往前面计算。真的很妙!

Code

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// time:O(n) space:O(n)
public int[] arr;
public int size;
public int max;
public _1381_DesignaStackWithIncrementOperation(int maxSize) {
size = 0;
max = maxSize;
arr = new int[1001];
}

public void push(int x) {
if (size < max) {
arr[size++] = x;
}
}

public int pop() {
if (size < 1) return -1;
int res = arr[size - 1];
size--;
return res;
}

public void increment(int k, int val) {
int j = k < size ? k : size;
for (int i = 0; i < j; i++) {
arr[i] += val;
}
}

// time: O(1) space:O(n)
int n;
int[] inc;
Stack<Integer> stack;
public CustomStack(int maxSize) {
n = maxSize;
inc = new int[n];
stack = new Stack<>();
}

public void push(int x) {
if (stack.size() < n) {
stack.push(x);
}
}

public int pop() {
int i = stack.size() - 1;
if (i < 0) return -1;
if (i > 0) inc[i - 1] += inc[i];
int res = stack.pop() + inc[i];
inc[i] = 0;
return res;
}

public void increment(int k, int val) {
int i = Math.min(k, stack.size()) - 1;
if (i >= 0)
inc[i] += val;
}

Reference