1381. Design a Stack With Increment Operation

how do we avoid incrementing k times?

use partial increment array to save increment number!

T: all O(1)

S: O(maxSize)

class CustomStack {

    private int[] increment;
    private LinkedList<Integer> list;
    private int maxSize;
    public CustomStack(int maxSize) {
        this.increment = new int[maxSize];
        this.list = new LinkedList();
        this.maxSize = maxSize;
    }
    
    public void push(int x) {
        if (list.size() >= maxSize) {
            return;
        }
        list.add(x);
    }
    
    public int pop() {
        if (list.isEmpty()) {
            return -1;
        }
        int curIndex = list.size()-1;
        int result = list.pollLast() + increment[curIndex];
        if (curIndex > 0) {
            increment[curIndex-1] += increment[curIndex];
        }
        increment[curIndex] = 0;
        return result;
    }
    
    public void increment(int k, int val) {
        if (list.isEmpty()) {
            return;
        }
        int index = Math.min(k, list.size()) - 1;
        increment[index] += val;
    }
}

/**

inc bottom k elements

O(1) for push & pop
O(1) for increment -> only apply increment for the pop number
but remember to copy this increment value to [index-1] (previous k-1)

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