1381. Design a stack that supports incremental operations.

Leetcode-cn.com/problems/de…

Topic describes

Please design a stack that supports the following operations. CustomStack: CustomStack(int maxSize) : Initializes the object with maxSize. MaxSize is the maximum number of elements in the stack. After the stack grows to maxSize, the push operation is not supported. Void push(int x) : If the stack has not grown to maxSize, x is added to the top of the stack. Int pop() : Pops the top element and returns the value at the top of the stack, or -1 if the stack is empty. Void inc(int k, int val) : void inc(int k, int val) : void inc(int k, int val) If the total number of elements in the stack is less than k, val is incremented for all elements in the stack. Example: Input:  ["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"] [[3], [1], [2], [], [2], [3], [4], [5100], [2100], [], [], [], []] output: [null, null, null, 2, null, null, null, null, null, 103202201, 1] : CustomStack CustomStack = new CustomStack (3); // Stack is empty [] customStack.push(1); // The stack changes to [1] customStack.push(2); // The stack changes to [1, 2] customStack.pop(); // Return 2 --> return the top value of the stack 2, the stack becomes [1] customStack.push(2); // The stack changes to [1, 2] customStack.push(3); // The stack changes to [1, 2, 3] customStack.push(4); // The stack is still [1, 2, 3], no other element can be added to change the stack size to 4 customStack.increment(5, 100); // Change the stack to [101, 102, 103] customStack.increment(2, 100); // The stack changes to [201, 202, 103] customStack.pop(); // Return 103 --> return the top value of the stack 103, the stack changes to [201, 202] customStack.pop(); // Return 202 --> return the top value of the stack 202, the stack becomes [201] customStack.pop(); // Return 201 --> return the top value of the stack to [] customStack.pop(); // Return -1 --> stack empty, return -1 message: 1 <= maxSize <= 1000 1 <= x <= 1000 1 <= k <= 1000 0 <= val <= 100 Each method increment, push and POP can be invoked at most 1000 times respectivelyCopy the code

Front knowledge

The company

  • no

Train of thought

The key point

code

  • Language support: Python3

Python3 Code:


class CustomStack:
    maxSize = 0
    stack = []

    def __init__(self, maxSize: int) :
        self.maxSize = maxSize
        self.stack = list(a)def push(self, x: int) - >None:
        if len(self.stack) < self.maxSize:
            self.stack.append(x)

    def pop(self) - >int:
        if len(self.stack) > 0:
            return self.stack.pop()
        else:
            return -1

    def increment(self, k: int, val: int) - >None:
        if len(self.stack) >= k:
            for i in range(0,k):
                self.stack[i] += val
        else:
            for i in range(len(self.stack)):
                self.stack[i] += val


# Your CustomStack object will be instantiated and called as such:
# obj = CustomStack(maxSize)
# obj.push(x)
# param_2 = obj.pop()
# obj.increment(k,val)


Copy the code

Complexity analysis

Let n be the length of the array.

  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)