实现一个支持增量操作的栈

题目描述：设计一个栈，除了支持常规的push、pop、top操作外，还需要支持一个增量操作increment(k, val)，该操作会将栈底部的k个元素（即最先入栈的k个元素）都增加val。如果栈中元素少于k个，则将栈中所有元素都增加val。要求所有操作的时间复杂度都是O(1)。

解题思路分析：
这个问题的难点在于increment操作需要修改栈底部的多个元素。如果直接遍历修改，时间复杂度为O(k)，不符合O(1)的要求。我们需要一种延迟更新的机制。

核心思想：使用两个栈

• 主栈：正常存储元素
• 增量栈：记录每个位置需要增加的累积值

详细步骤：

1. 数据结构设计

class CustomStack:
    def __init__(self, maxSize: int):
        self.stack = []  # 主栈，存储实际元素
        self.inc = []   # 增量栈，记录每个位置的累积增量
        self.max_size = maxSize

2. push操作

def push(self, x: int) -> None:
    if len(self.stack) < self.max_size:
        self.stack.append(x)
        self.inc.append(0)  # 新元素初始增量为0

3. pop操作

def pop(self) -> int:
    if not self.stack:
        return -1
    
    # 获取当前元素的增量值
    index = len(self.stack) - 1
    inc_val = self.inc[index]
    
    # 如果前面还有元素，将增量传递给前一个元素
    if index > 0:
        self.inc[index-1] += inc_val
    
    # 弹出元素并返回（加上其增量）
    self.inc.pop()
    return self.stack.pop() + inc_val

4. increment操作

def increment(self, k: int, val: int) -> None:
    if not self.stack:
        return
    
    # 确定实际要更新的位置
    index = min(k, len(self.stack)) - 1
    # 在增量栈的对应位置记录增量
    self.inc[index] += val

完整代码实现：

class CustomStack:
    def __init__(self, maxSize: int):
        self.stack = []
        self.inc = []
        self.max_size = maxSize

    def push(self, x: int) -> None:
        if len(self.stack) < self.max_size:
            self.stack.append(x)
            self.inc.append(0)

    def pop(self) -> int:
        if not self.stack:
            return -1
        
        index = len(self.stack) - 1
        inc_val = self.inc[index]
        
        if index > 0:
            self.inc[index-1] += inc_val
        
        self.inc.pop()
        return self.stack.pop() + inc_val

    def increment(self, k: int, val: int) -> None:
        if not self.stack:
            return
        
        index = min(k, len(self.stack)) - 1
        self.inc[index] += val

算法正确性分析：

• 当执行increment(k, val)时，我们只在第min(k, n)-1个位置记录增量
• 在pop时，当前元素的增量会被加到返回值中，同时将增量传递给前一个元素
• 这种"延迟传递"的机制确保了每个元素在弹出时都能获得正确的累积增量

时间复杂度分析：

• push: O(1)
• pop: O(1)
• increment: O(1)
  所有操作都满足O(1)时间复杂度要求

这种设计巧妙地利用了"延迟更新"的思想，将批量更新的操作分摊到每个pop操作中，从而保证了所有操作的时间复杂度都是O(1)。