dsa/min_stack.py at main · 121watts/dsa · GitHub

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
from math import inf

class MinStack:
    def __init__(self):
        self.min = inf
        self.stack = []
        self.mins = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        self._setMin(val)

    def pop(self) -> None:
        self.stack.pop()
        self._nextMin()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min

    def _setMin(self, val) -> None:
        self.min = min(self.min, val)
        self.mins.append(self.min)

    def _nextMin(self):
        self.mins.pop()

        if len(self.mins):
            self.min = self.mins[-1]
        else:
            self.min = inf

ms = MinStack()

# ["MinStack", "push", 0, "push", -1, "push", 0, "pop", "getMin", "pop", "getMin"]


ms.push(0)
ms.push(-1)
ms.push(0)
ms.pop()
print(ms.getMin())
ms.pop()
print(ms.getMin())
print('stack:', ms.stack)
print('mins:', ms.mins)