Algorithm-LeetCode/Solutions/0155.Min_Stack.py at main · ling67/Algorithm-LeetCode · 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
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
/*
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.


Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

*/


/*
there are two method to solve this problem
approch 1: we can use stack store the min value, each time we push number to stack, we store the min value in stack as well
approch 2: we use two stack, one can be use to store value, the other one can be use to store min value.
*/

#approach 2
class MinStack:

    def __init__(self):
        self.st = []
        self.min_st = []

    def push(self, val: int) -> None:
        self.st.append(val)
        if len(self.min_st) == 0 or val <= self.min_st[-1]:
            self.min_st.append(val)

    def pop(self) -> None:
        if len(self.st) == 0:
            raise IndexError("The stack is empty")
        else:
            val = self.st.pop()
            if val == self.min_st[-1]:
                self.min_st.pop()
        return val

    def top(self) -> int:
        if len(self.st) == 0:
            raise IndexError("The stack is empty")
        return self.st[-1]

    def getMin(self) -> int:
        if len(self.st) == 0:
            raise IndexError("The stack is empty")
        return self.min_st[-1]


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

class MinStack:

    def __init__(self):
        self.st = []

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

    def pop(self) -> None:
        if len(self.st) == 0:
            raise IndexError("The stack is empty!")
        return self.st.pop()

    def top(self) -> int:
        if len(self.st) == 0:
            raise IndexError("The stack is empty!")
        return self.st[-1]

    def getMin(self) -> int:   #注意没有说删除最小值
        if len(self.st) == 0:
            raise IndexError("The stack is empty!")
        minValue = min(self.st)
        return minValue


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()