【Day 3】1381. 设计一个支持增量操作的栈.md

思路

用数组模拟栈的操作，top记录栈顶的位置。

代码

class CustomStack {
    //第一种
    int[] stack;
    int top;
    public CustomStack(int maxSize) {
        stack = new int[maxSize];
        top = -1;
    }
    
    public void push(int x) {
        if(top < stack.length - 1){
            stack[++top] = x;
        }
    }
    
    public int pop() {
        // if(top > -1){
        //     int res = stack[top];
        //     stack[top--] = 0;
        //     return res;
        // }else{
        //     return -1;
        // }
        if(top == -1){
            return -1;
        }
        return stack[top--];

    }
    
    public void increment(int k, int val) {
        // if(top < k - 1){
        //     k = top + 1;
        // }
        k = Math.min(k, top + 1);
        for(int i = 0; i < k; i++){
            stack[i] += val;
        }
    }
}

复杂度分析

• 时间复杂度：初始化、push、pop操作均为O(1)，inc操作为O(k)。
• 空间复杂度：O(maxSize)，使用了额外长度为maxSize的数组stack。