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 constructor(maxSize) {
3 this.stack = [];
4 this.maxSize = maxSize;
5 }
6
7 push(x) {
8 if (this.stack.length < this.maxSize) {
9 this.stack.push(x);
10 }
11 }
12
13 pop() {
14 if (this.stack.length === 0) {
15 return -1;
16 }
17 return this.stack.pop();
18 }
19
20 increment(k, val) {
21 for (let i = 0; i < Math.min(k, this.stack.length); i++) {
22 this.stack[i] += val;
23 }
24 }
25}The CustomStack class in JavaScript uses an array as the underlying storage for the stack. The methods push, pop, and increment are implemented similarly to the Python version, ensuring that operations stay within the maxSize constraints and using a loop to increment elements.
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.