LeetcodeSol/Top_100_Liked_Questions/MinStack.cpp at master · CedricXing/LeetcodeSol · 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
#include <stack>
#include <climits>
using namespace std;

/* Sol
* Using two stacks, min_st to store the min values
*/
class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> st;
    stack<int> min_st;
    MinStack() {
    }

    void push(int x) {
        if(st.empty() || x <= min_st.top()){
            min_st.push(x);
        }
        st.push(x);
    }

    void pop() {
        if(st.top() == min_st.top()){
            min_st.pop();
        }
        st.pop();
    }

    int top() {
        return st.top();
    }

    int getMin() {
        return min_st.top();
    }
};

/* Sol 1
* Only use one stack.
* When a new min_value occured, push the old min value.
* Very smart solution!!!
*/

class MinStack1 {
public:
    /** initialize your data structure here. */
    stack<int> st;
    int min;
    MinStack1() {
        min = INT_MAX;
    }

    void push(int x) {
        if(x <= min){
            st.push(min);
            min = x;
        }
        st.push(x);
    }

    void pop() {
        if(st.top() == min){
            st.pop();
            min = st.top();
        }
        st.pop();
    }

    int top() {
        return st.top();
    }

    int getMin() {
        return min;
    }
};