Sponsored
Sponsored
This approach uses a direct array implementation to handle all operations. A list or array is used as the underlying data structure for the stack, and operations are directly performed on the stack as specified. This results in a direct and straightforward implementation, where increment operations iterate over the bottom k elements to increment them by the given value.
Time Complexity: O(k) for the increment operation, O(1) for the push and pop operations.
Space Complexity: O(n) where n is the max size of the stack.
1class CustomStack:
2 def __init__(self, maxSize: int):
3 self.stack = []
4 self.maxSize = maxSize
5
6 def push(self, x: int) -> None:
7 if len(self.stack) < self.maxSize:
8 self.stack.append(x)
9
10 def pop(self) -> int:
11 if len(self.stack) == 0:
12 return -1
13 return self.stack.pop()
14
15 def increment(self, k: int, val: int) -> None:
16 for i in range(min(k, len(self.stack))):
17 self.stack[i] += valThe CustomStack class keeps a list stack which is the container for stack elements. maxSize is the maximum capacity for the stack. In the push method, the element is added if the stack has not exceeded the set maxSize. The pop method removes and returns the top element or -1 if the stack is empty. In the increment method, the bottom k elements are incremented by iterating through each and adding the given val.
This approach uses an auxiliary array to optimize the increment operation by storing lazy increments and applying them during the pop operation. This lazy approach ensures that increments do not have to iterate over the stack directly, thus reducing potential redundant operations.
Time Complexity: O(1) for push and pop; O(1) amortized for increment.
Space Complexity: O(n) where n is the max size of the stack.
1class CustomStack {
2 private int
The Java CustomStack class uses arrays for both stack and increment. Top is an index marker for the top of the stack. Lazy increments are applied when pop is called using the same logic as in the C++ solution, where each element’s increment value is propagated down as necessary.