Leetcode 1381.设计一个支持增量操作的栈
1 题目描述(Leetcode题目链接) 【Leetcode 1381.设计一个支持增量操作的栈(Design a Stack With Increment Operation)】??请你设计一个支持下述操作的栈。
实现自定义栈类 CustomStack :
- CustomStack(int maxSize):用 maxSize 初始化对象,maxSize 是栈中最多能容纳的元素数量,栈在增长到 maxSize 之后则不支持 push 操作。
- void push(int x):如果栈还未增长到 maxSize ,就将 x 添加到栈顶。
- int pop():弹出栈顶元素,并返回栈顶的值,或栈为空时返回 -1 。
- void inc(int k, int val):栈底的 k 个元素的值都增加 val 。如果栈中元素总数小于 k ,则栈中的所有元素都增加 val 。
输入:
["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
输出:
[null,null,null,2,null,null,null,null,null,103,202,201,-1]
解释:
CustomStack customStack = new CustomStack(3);
// 栈是空的 []
customStack.push(1);
// 栈变为 [1]
customStack.push(2);
// 栈变为 [1, 2]
customStack.pop();
// 返回 2 --> 返回栈顶值 2,栈变为 [1]
customStack.push(2);
// 栈变为 [1, 2]
customStack.push(3);
// 栈变为 [1, 2, 3]
customStack.push(4);
// 栈仍然是 [1, 2, 3],不能添加其他元素使栈大小变为 4
customStack.increment(5, 100);
// 栈变为 [101, 102, 103]
customStack.increment(2, 100);
// 栈变为 [201, 202, 103]
customStack.pop();
// 返回 103 --> 返回栈顶值 103,栈变为 [201, 202]
customStack.pop();
// 返回 202 --> 返回栈顶值 202,栈变为 [201]
customStack.pop();
// 返回 201 --> 返回栈顶值 201,栈变为 []
customStack.pop();
// 返回 -1 --> 栈为空,返回 -1
提示:
- 1 <= maxSize <= 1000
- 1 <= x <= 1000
- 1 <= k <= 1000
- 0 <= val <= 100
- 每种方法 increment,push 以及 pop 分别最多调用 1000 次
class CustomStack:def __init__(self, maxSize: int):
self.size = maxSize
self.stack = []def push(self, x: int) -> None:
if len(self.stack) == self.size:
return
self.stack.append(x)def pop(self) -> int:
return self.stack.pop() if self.stack else -1def increment(self, k: int, val: int) -> None:
for i in range(min(k, len(self.stack))):
self.stack[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)
参考官方题解,通过一个额外的列表来讲增量操作的时间复杂度降低为 O ( 1 ) O(1) O(1),因为我们只在pop操作的时候才用得到增量带来的元素变化。
class CustomStack:def __init__(self, maxSize: int):
self.size = maxSize
self.stack = [0]*self.size
self.add = [0]*self.size
self.top = -1def push(self, x: int) -> None:
if self.top < self.size - 1:
self.top += 1
self.stack[self.top] = xdef pop(self) -> int:
if self.top == -1:
return -1
res = self.stack[self.top] + self.add[self.top]
if self.top:
self.add[self.top - 1] += self.add[self.top]
self.add[self.top] = 0
self.top -= 1
return resdef increment(self, k: int, val: int) -> None:
i = min(self.top, k-1)
if i >= 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)
推荐阅读
- 数据结构与算法|【算法】力扣第 266场周赛
- leetcode|今天开始记录自己的力扣之路
- Python|Python 每日一练 二分查找 搜索旋转排序数组 详解
- 【LeetCode】28.实现strstr() (KMP超详细讲解,sunday解法等五种方法,java实现)
- LeetCode-35-搜索插入位置-C语言
- leetcode python28.实现strStr()35. 搜索插入位置
- Leetcode Permutation I & II
- python|leetcode Longest Substring with At Most Two Distinct Characters 滑动窗口法
- LeetCode 28 Implement strStr() (C,C++,Java,Python)
- Python|Python Leetcode(665.非递减数列)