自己的做法
算法思想
因为要有增量操作,所以所有的元素应该都是可见的。所以肯定不能用栈,可以使用数组。
并用一个index变量,来表示数组最后一个元素的索引,相当于指向栈顶元素。
inc操作,就直接比较k - 1和index的大小,较小值为min,从0到min的每个元素都加上val即可。
算法实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| class CustomStack { private: vector<int> nums; int index = -1; public: CustomStack(int maxSize) { nums.resize(maxSize); }
void push(int x) { if(index != nums.size() - 1) { nums[++index] = x; } }
int pop() { if (index == -1) { return -1; } return nums[index--];
}
void increment(int k, int val) { int min = k < index ? k : index; for(int i = 0; i < min; i++) { nums[i] += val; } } };
|
性能分析
时间复杂度:push和pop操作为O(1),increment操作为O(n)。
参考做法
有两种,第一种和我的相同。
只说第二种。
算法思想
同样使用数组来做。
push和pop操作时间复杂度都是$$O(1)$$,所以要优化inc操作,使它的时间复杂度降为$$O(1)$$。
可以添加一个数组add,add[i]就是nums[i]应该要增加的值。
并且如果k个元素加1,将k - 1和index比较,较小值为min,我们知道从0 到 min的元素都要加1,所以我们可以只给第 min个元素加1,即add[min] = 1。
当要弹出栈顶元素时,就返回nums[index] + add[index]
,即它原来的值和应该增加的值。
并且将add[index]加到add[index - 1]上。
也就是说,每个元素只有在弹出的时候,才会知道它实际的值。
例如:maxSize是3。
首先插入三个数字 1 2 3。这时栈为 1 2 3。add数组为 0 0 0。
然后执行inc(3, 1)
, inc(2, 1)
, inc(1, 1)
。即栈底3个元素、2个元素、1个元素分别加1。三个元素值都应为4
这时add数组变为:1 1 1。当弹出栈顶元素3时,弹出3 + 1 = 4
。并将add[index]加到add[index - 1]上,然后add[index]置为0。这时候add数组变为 1 2 0。
再弹出2,应该是 2 + 2= 4
。add数组变为3 0 0。最后弹出1 + 3 = 4
。
算法实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| class CustomStack { private: vector<int> nums; vector<int> add; int index = -1; public: CustomStack(int maxSize) { nums.resize(maxSize); add.resize(maxSize); }
void push(int x) { if(index != nums.size() - 1) { nums[++index] = x; } }
int pop() { if (index == -1) { return -1; } int res = nums[index] + add[index]; if(index != 0) { add[index - 1] += add[index]; } add[index] = 0; index--; return res;
}
void increment(int k, int val) { int min = k - 1 < index ? k - 1 : index; if(min >= 0) { add[min] += val; } } };
|
性能分析
时间复杂度:三个操作都是O(1)。