一步一步对比！将常规做法转为累加操作

常规做法主要是increment方法内部比较k与当前栈长度然后遍历栈修改内部值, 这个想必大家都会做。

class CustomStack:

    def __init__(self, maxSize: int):
        self.stack = []
        self.length_stack = 0
        self.maxSize = maxSize

    def push(self, x: int) -> None:
        if self.length_stack < self.maxSize:
            self.stack.append(x)
            self.length_stack += 1
    def pop(self) -> int:
        if self.length_stack:
            self.length_stack -= 1
            return self.stack.pop()
        else:
            return -1

    def increment(self, k: int, val: int) -> None:
        min_index = min(k, self.length_stack)
        for i in range(min_index):
            self.stack[i] += val

那么优化点在哪里？可以发现元素仅在pop时才会输出，那么我们是否有必要每当有增量就立即修改内部值呢？
要知道pop每次只输出栈顶元素(列表结尾),那么是不是可以存储增量当pop元素时才累加到原始值上呢？

1. __init__方法定义的初始值(属性)不变
   • 栈
   • 栈长度
   • maxSize
2. push()方法 变化点在于将stack.append(x)-->stack.append([x,0]) 对应元素值与增量 刚开始增量都为0
3. increment()方法变化比较多,将旧的遍历累加 –> 将mind_index位置的增量累加val即可
4. pop()方法是重点，1) 长度-1 2）获取当前值与增量 3) 对当前项的上一项的增量累加当前项元素的增量 4）返回当前值+增量

举个栗子：

• [1，2，3] 前三个元素+10 然后前两个元素+10 这时栈内怎么保存的呢 [[1,0],[2,10],[3,10]]
• 弹出3时 返回3+10 然后对当前项的上一项的增量累加当前项元素的增量 也就是 2的增量10+当前3的增量10 = 20
• 弹出2时 返回2+20 然后对当前项的上一项的增量累加当前项元素的增量 也就是 1的增量0+当前2的增量20= 20
• 弹出1时 直接弹出 1+20

class CustomStack:

    def __init__(self, maxSize: int):
        self.stack = []
        self.length_stack = 0
        self.maxSize = maxSize

    def push(self, x: int) -> None:
        if self.length_stack < self.maxSize:
            self.stack.append([x, 0])
            self.length_stack += 1

    def pop(self) -> int:
        if self.length_stack:
            self.length_stack -= 1
            current_x, inc = self.stack.pop()
            if self.length_stack >= 1:
                self.stack[-1][1] += inc
            return current_x + inc
        return -1

    def increment(self, k: int, val: int) -> None:
        if self.length_stack > 0:
            k -= 1
            min_index = min(k, self.length_stack-1)
            self.stack[min_index][1] += val

作者：hello_lwz
链接：https://leetcode-cn.com/problems/design-a-stack-with-increment-operation/solution/yi-bu-yi-bu-dui-bi-jiang-chang-gui-zuo-fa-zhuan-we/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。