Link to LeetCode Problem

S1: 模拟

直观思路是在增量操作时进行模拟，每次进行增量操作时都遍历指定的 k 个元素，但这样时间复杂度是 $O(N)$。

时间优化思路是，既然我们只有在出栈时才考虑元素的值，何不将增量操作延后到出栈时，如此便需要将所有增量操作都先存起来。

• 借助另一个容器来记录增量操作。
• 在出栈时，将栈顶元素加上增量弹出，并更新增量记录。

class CustomStack {
public:
    CustomStack(int maxSize): max_size_(maxSize) {
        stack_.resize(maxSize);
        add_.resize(maxSize);
    }
    
    void push(int x) {
        if (top_ < max_size_ - 1) {
            top_++;
            stack_[top_] = x;
        }
    }
    
    int pop() {
        if (top_ == -1) return -1;
        int res = stack_[top_] + add_[top_];
        if (top_ > 0) add_[top_ - 1] += add_[top_];
        add_[top_] = 0; 
        top_--;
        return res;

    }
    
    void increment(int k, int val) {
        int idx = min(k - 1, top_);
        if (idx >= 0) add_[idx] += val;
    }
private:
    vector<int> stack_;
    vector<int> add_;
    int top_ = -1;
    int max_size_;
};

/**
 * 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);
 */

• Time: $O(1)$，所有操作的时间复杂度都是 $O(1)$。
• Space: $O(N)$，使用了一个长度为 maxSize 的辅助数组来记录增量操作。