-
Notifications
You must be signed in to change notification settings - Fork 22
Expand file tree
/
Copy path155.min-stack.cpp
More file actions
107 lines (93 loc) · 2.28 KB
/
155.min-stack.cpp
File metadata and controls
107 lines (93 loc) · 2.28 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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
// Tag: Stack, Design
// Time: O(1)
// Space: O(N)
// Ref: -
// Note: -
// 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.
//
// You must implement a solution with O(1) time complexity for each function.
//
// 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
//
//
// Constraints:
//
// -231 <= val <= 231 - 1
// Methods pop, top and getMin operations will always be called on non-empty stacks.
// At most 3 * 104 calls will be made to push, pop, top, and getMin.
//
//
class MinStack {
stack<pair<int, int>> st;
public:
MinStack() {
}
void push(int val) {
int cur_min = st.empty() ? INT_MAX: getMin();
st.push(make_pair(val, min(cur_min, val)));
}
void pop() {
st.pop();
}
int top() {
pair<int, int> p = st.top();
return p.first;
}
int getMin() {
pair<int, int> p = st.top();
return p.second;
}
};
class MinStack {
stack<int> st, mini;
public:
MinStack() {
}
void push(int val) {
int cur_min = st.empty() ? INT_MAX: getMin();
mini.push(min(cur_min, val));
st.push(val);
}
void pop() {
mini.pop();
st.pop();
}
int top() {
return st.top();
}
int getMin() {
return mini.top();
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/