-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathDesignAStackWithIncrementOperation.py
More file actions
90 lines (70 loc) · 3.71 KB
/
Copy pathDesignAStackWithIncrementOperation.py
File metadata and controls
90 lines (70 loc) · 3.71 KB
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
"""
https://leetcode.com/problems/design-a-stack-with-increment-operation/
Design a stack which supports the following operations.
Implement the CustomStack class:
CustomStack(int maxSize) Initializes the object with maxSize which is the maximum number of elements in the stack or do nothing if the stack reached the maxSize.
void push(int x) Adds x to the top of the stack if the stack hasn't reached the maxSize.
int pop() Pops and returns the top of 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, just 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 customStack = new CustomStack(3); // Stack is Empty []
customStack.push(1); // stack becomes [1]
customStack.push(2); // stack becomes [1, 2]
customStack.pop(); // return 2 --> Return top of the stack 2, stack becomes [1]
customStack.push(2); // stack becomes [1, 2]
customStack.push(3); // stack becomes [1, 2, 3]
customStack.push(4); // stack still [1, 2, 3], Don't add another elements as size is 4
customStack.increment(5, 100); // stack becomes [101, 102, 103]
customStack.increment(2, 100); // stack becomes [201, 202, 103]
customStack.pop(); // return 103 --> Return top of the stack 103, stack becomes [201, 202]
customStack.pop(); // return 202 --> Return top of the stack 102, stack becomes [201]
customStack.pop(); // return 201 --> Return top of the stack 101, stack becomes []
customStack.pop(); // return -1 --> Stack is empty return -1.
Constraints:
1 <= maxSize <= 1000
1 <= x <= 1000
1 <= k <= 1000
0 <= val <= 100
At most 1000 calls will be made to each method of increment, push and pop each separately.
Use an array to represent the stack. Push will add new integer to the array. Pop removes the last element in the array and increment will add val to the first k elements of the array.
This solution run in O(1) per push and pop and O(k) per increment.
"""
from Common.Constants import null
from Common.ObjectTestingUtils import run_object_tests
# Runtime: 140 ms, faster than 42.18% of Python3 online submissions for Design a Stack With Increment Operation.
# Memory Usage: 15.1 MB, less than 18.84% of Python3 online submissions for Design a Stack With Increment Operation.
class CustomStack:
def __init__(self, maxSize: int):
self.items = []
self.maxSize = maxSize
def push(self, x: int) -> None:
if len(self.items) == self.maxSize:
return
self.items.append(x)
def pop(self) -> int:
if not self.items:
return -1
return self.items.pop()
def increment(self, k: int, val: int) -> None:
k = min(k, len(self.items))
for i in range(k):
self.items[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)
tests = [
[
["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]
]
]
run_object_tests(tests, cls=CustomStack)