68-支持增量操作的栈

自己的做法

算法思想

因为要有增量操作，所以所有的元素应该都是可见的。所以肯定不能用栈，可以使用数组。

并用一个index变量，来表示数组最后一个元素的索引，相当于指向栈顶元素。

inc操作，就直接比较k - 1和index的大小，较小值为min，从0到min的每个元素都加上val即可。

算法实现

class CustomStack {
private:
    vector<int> nums;
    int index = -1;
public:
    CustomStack(int maxSize) {
        nums.resize(maxSize);
    }

    void push(int x) {
        if(index != nums.size() - 1) {
            nums[++index] = x;
        }
    }

    int pop() {
        if (index == -1) {
            return -1;
        }
        return nums[index--];

    }

    void increment(int k, int val) {
        int min = k < index ? k : index;
        for(int i = 0; i < min; i++) {
            nums[i] += val;
        }
    }
};

性能分析

时间复杂度：push和pop操作为$O(1)$，increment操作为$O(n)$。

参考做法

有两种，第一种和我的相同。

只说第二种。

算法思想

同样使用数组来做。

push和pop操作时间复杂度都是$$O(1)$$，所以要优化inc操作，使它的时间复杂度降为$$O(1)$$。

可以添加一个数组add，add[i]就是nums[i]应该要增加的值。

并且如果k个元素加1，将k - 1和index比较，较小值为min，我们知道从0 到 min的元素都要加1，所以我们可以只给第 min个元素加1，即add[min] = 1。

当要弹出栈顶元素时，就返回nums[index] + add[index]，即它原来的值和应该增加的值。

并且将add[index]加到add[index - 1]上。

也就是说，每个元素只有在弹出的时候，才会知道它实际的值。

例如：maxSize是3。

首先插入三个数字 1 2 3。这时栈为 1 2 3。add数组为 0 0 0。

然后执行inc(3, 1), inc(2, 1), inc(1, 1)。即栈底3个元素、2个元素、1个元素分别加1。三个元素值都应为4

这时add数组变为：1 1 1。当弹出栈顶元素3时，弹出3 + 1 = 4。并将add[index]加到add[index - 1]上，然后add[index]置为0。这时候add数组变为 1 2 0。

再弹出2，应该是 2 + 2= 4。add数组变为3 0 0。最后弹出1 + 3 = 4。

算法实现

class CustomStack {
private:
    vector<int> nums;
    vector<int> add;
    int index = -1;
public:
    CustomStack(int maxSize) {
        nums.resize(maxSize);
        add.resize(maxSize);
    }

    void push(int x) {
        if(index != nums.size() - 1) {
            nums[++index] = x;
        }
    }

    int pop() {
        if (index == -1) {
            return -1;
        }
        int res = nums[index] + add[index];
        if(index != 0) {
            // 将待弹出的元素要增加的值加到下一个栈顶元素的add数组对应位置
            add[index - 1] += add[index];
        }
        add[index] = 0;
        index--;
        return res;

    }

    void increment(int k, int val) {
        // 取 k - 1和index的较小值
        int min = k - 1 < index ? k - 1 : index;
        if(min >= 0) {
            add[min] += val;
        }
    }
};

性能分析

时间复杂度：三个操作都是$O(1)$。