Short Problem Definition:
You have an empty sequence, and you will be given N queries. Each query is one of these three types:
- Push the element x into the stack.
- Delete the element present at the top of the stack.
- Print the maximum element in the stack.
Link
Complexity:
time complexity is O(N)
space complexity is O(N)
Execution:
I really enjoyed this problem. I did not see the solution at first, but after it popped up, it was really simple.
Keep two stacks. One for the actual values and one (non-strictly) increasing stack for keeping the maxima.
Solution:
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: def __init__( self ): self .stack = [] self .maxima = [] def push( self , value): self .stack.append(value) if not self .maxima or value > = self .maxima[ - 1 ]: self .maxima.append(value) def printMax( self ): print self .maxima[ - 1 ] def pop( self ): value = self .stack.pop() if value = = self .maxima[ - 1 ]: self .maxima.pop() def main(): cs = CustomStack() N = int ( raw_input ()) for _ in xrange (N): unknown = raw_input () command = unknown[ 0 ] if command = = '1' : cmd, value = map ( int , unknown.split()) cs.push(value) elif command = = '2' : cs.pop() else : cs.printMax() if __name__ = = '__main__' : main() |