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.
1#include <vector>
2
3class CustomStack {
4 std::vector<int> stack;
5 std::vector<int> increment;
int maxSize;
public:
CustomStack(int maxSize) : maxSize(maxSize) {
increment.resize(maxSize, 0);
}
void push(int x) {
if (stack.size() < maxSize) {
stack.push_back(x);
}
}
int pop() {
int idx = stack.size() - 1;
if (idx < 0) return -1;
int result = stack[idx] + increment[idx];
if (idx > 0) increment[idx - 1] += increment[idx];
increment[idx] = 0;
stack.pop_back();
return result;
}
void increment(int k, int val) {
int i = std::min(k, (int)stack.size()) - 1;
if (i >= 0) increment[i] += val;
}
};In this C++ implementation, a CustomStack includes two vectors: stack for the elements and increment for storing lazy increments. Increments are applied when popping an element, allowing lazy updates using increment[idx] to distribute the incremented value. The increment array propagates the increments when an element is popped.