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

// 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

• https://leetcode.com/problems/design-a-stack-with-increment-operation/discuss/539716/JavaC%2B%2BPython-Lazy-increment-O(1)