Design a stack that supports increment operations on its elements.
Implement the CustomStack class:
CustomStack(int maxSize) Initializes the object with maxSize which is the maximum number of elements in the stack.
void push(int x) Adds x to the top of the stack if the stack has not reached the maxSize.
int pop() Pops and returns the top of the stack or -1 if the stack is empty.
void inc(int k, int val) Increments the bottom k elements of the stack by val. If there are less than k elements in the stack, increment all the elements in the stack.
Example 1:
Input
["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
Output
[null,null,null,2,null,null,null,null,null,103,202,201,-1]
Explanation
CustomStack stk = new CustomStack(3); // Stack is Empty []
stk.push(1); // stack becomes [1]
stk.push(2); // stack becomes [1, 2]
stk.pop(); // return 2 --> Return top of the stack 2, stack becomes [1]
stk.push(2); // stack becomes [1, 2]
stk.push(3); // stack becomes [1, 2, 3]
stk.push(4); // stack still [1, 2, 3], Do not add another elements as size is 4
stk.increment(5, 100); // stack becomes [101, 102, 103]
stk.increment(2, 100); // stack becomes [201, 202, 103]
stk.pop(); // return 103 --> Return top of the stack 103, stack becomes [201, 202]
stk.pop(); // return 202 --> Return top of the stack 202, stack becomes [201]
stk.pop(); // return 201 --> Return top of the stack 201, stack becomes []
stk.pop(); // return -1 --> Stack is empty return -1.
Constraints:
1 <= maxSize, x, k <= 1000
0 <= val <= 100
At most 1000 calls will be made to each method of increment, push and pop each separately.
Solutions
Solution 1: Array Simulation
We can use an array $stk$ to simulate the stack, and an integer $i$ to represent the position of the next element to be pushed into the stack. In addition, we need another array $add$ to record the cumulative increment value at each position.
When calling $push(x)$, if $i < maxSize$, we put $x$ into $stk[i]$ and increment $i$ by one.
When calling $pop()$, if $i \leq 0$, it means the stack is empty, so we return $-1$. Otherwise, we decrement $i$ by one, and the answer is $stk[i] + add[i]$. Then we add $add[i]$ to $add[i - 1]$, and set $add[i]$ to zero. Finally, we return the answer.
When calling $increment(k, val)$, if $i > 0$, we add $val$ to $add[\min(i, k) - 1]$.
The time complexity is $O(1)$, and the space complexity is $O(n)$. Where $n$ is the maximum capacity of the stack.
classCustomStack:def__init__(self,maxSize:int):self.stk=[0]*maxSizeself.add=[0]*maxSizeself.i=0defpush(self,x:int)->None:ifself.i<len(self.stk):self.stk[self.i]=xself.i+=1defpop(self)->int:ifself.i<=0:return-1self.i-=1ans=self.stk[self.i]+self.add[self.i]ifself.i>0:self.add[self.i-1]+=self.add[self.i]self.add[self.i]=0returnansdefincrement(self,k:int,val:int)->None:i=min(k,self.i)-1ifi>=0:self.add[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)
classCustomStack{privateint[]stk;privateint[]add;privateinti;publicCustomStack(intmaxSize){stk=newint[maxSize];add=newint[maxSize];}publicvoidpush(intx){if(i<stk.length){stk[i++]=x;}}publicintpop(){if(i<=0){return-1;}intans=stk[--i]+add[i];if(i>0){add[i-1]+=add[i];}add[i]=0;returnans;}publicvoidincrement(intk,intval){if(i>0){add[Math.min(i,k)-1]+=val;}}}/** * Your CustomStack object will be instantiated and called as such: * CustomStack obj = new CustomStack(maxSize); * obj.push(x); * int param_2 = obj.pop(); * obj.increment(k,val); */
classCustomStack{public:CustomStack(intmaxSize){stk.resize(maxSize);add.resize(maxSize);i=0;}voidpush(intx){if(i<stk.size()){stk[i++]=x;}}intpop(){if(i<=0){return-1;}intans=stk[--i]+add[i];if(i>0){add[i-1]+=add[i];}add[i]=0;returnans;}voidincrement(intk,intval){if(i>0){add[min(k,i)-1]+=val;}}private:vector<int>stk;vector<int>add;inti;};/** * Your CustomStack object will be instantiated and called as such: * CustomStack* obj = new CustomStack(maxSize); * obj->push(x); * int param_2 = obj->pop(); * obj->increment(k,val); */
typeCustomStackstruct{stk[]intadd[]intiint}funcConstructor(maxSizeint)CustomStack{returnCustomStack{make([]int,maxSize),make([]int,maxSize),0}}func(this*CustomStack)Push(xint){ifthis.i<len(this.stk){this.stk[this.i]=xthis.i++}}func(this*CustomStack)Pop()int{ifthis.i<=0{return-1}this.i--ans:=this.stk[this.i]+this.add[this.i]ifthis.i>0{this.add[this.i-1]+=this.add[this.i]}this.add[this.i]=0returnans}func(this*CustomStack)Increment(kint,valint){ifthis.i>0{this.add[min(k,this.i)-1]+=val}}/** * Your CustomStack object will be instantiated and called as such: * obj := Constructor(maxSize); * obj.Push(x); * param_2 := obj.Pop(); * obj.Increment(k,val); */
classCustomStack{privatestk:number[];privateadd:number[];privatei:number;constructor(maxSize:number){this.stk=Array(maxSize).fill(0);this.add=Array(maxSize).fill(0);this.i=0;}push(x:number):void{if(this.i<this.stk.length){this.stk[this.i++]=x;}}pop():number{if(this.i<=0){return-1;}constans=this.stk[--this.i]+this.add[this.i];if(this.i>0){this.add[this.i-1]+=this.add[this.i];}this.add[this.i]=0;returnans;}increment(k:number,val:number):void{if(this.i>0){this.add[Math.min(this.i,k)-1]+=val;}}}/** * Your CustomStack object will be instantiated and called as such: * var obj = new CustomStack(maxSize) * obj.push(x) * var param_2 = obj.pop() * obj.increment(k,val) */