1381. 设计一个支持增量操作的栈
1381. 设计一个支持增量操作的栈
题目
Design a stack that supports increment operations on its elements.
Implement the CustomStack
class:
CustomStack(int maxSize)
Initializes the object withmaxSize
which is the maximum number of elements in the stack.void push(int x)
Addsx
to the top of the stack if the stack has not reached themaxSize
.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 bottomk
elements of the stack byval
. If there are less thank
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 ofincrement
,push
andpop
each separately.
题目大意
请你设计一个支持对其元素进行增量操作的栈。
实现自定义栈类 CustomStack
:
CustomStack(int maxSize)
:用maxSize
初始化对象,maxSize
是栈中最多能容纳的元素数量。void push(int x)
:如果栈还未增长到maxSize
,就将x
添加到栈顶。int pop()
:弹出栈顶元素,并返回栈顶的值,或栈为空时返回-1
。void inc(int k, int val)
:栈底的k
个元素的值都增加val
。如果栈中元素总数小于k
,则栈中的所有元素都增加val
。
解题思路
按照题目要求实现即可:
- 对于
push
操作,首先判断当前元素的个数是否达到上限,如果没有达到,就把top
后移一个位置并添加一个元素。 - 对于
pop
操作,首先判断当前栈是否为空,非空返回栈顶元素并将top
前移一位,否则返回−1
。 - 对于
inc
操作,直接对栈底的最多k
个元素加上val
。
复杂度分析
- 时间复杂度:初始化(构造函数)、
push
操作和pop
操作的渐进时间复杂度为O(1)
,inc
操作的渐进时间复杂度为O(k)
。 - 空间复杂度:这里用到了一个长度为
maxSize
的数组作为辅助空间,渐进空间复杂度为O(maxSize)
。
代码
/**
* @param {number} maxSize
*/
var CustomStack = function (maxSize) {
this.stack = [];
this.max = maxSize;
};
/**
* @param {number} x
* @return {void}
*/
CustomStack.prototype.push = function (x) {
if (this.stack.length < this.max) {
this.stack.push(x);
}
};
/**
* @return {number}
*/
CustomStack.prototype.pop = function () {
if (this.stack.length > 0) {
return this.stack.pop();
}
return -1;
};
/**
* @param {number} k
* @param {number} val
* @return {void}
*/
CustomStack.prototype.increment = function (k, val) {
k = Math.min(k, this.stack.length);
for (let i = 0; i < k; i++) {
this.stack[i] += 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)
*/