It’s been almost two years since I last practiced problems, and the pressure is huge. I’ve been practicing recently to keep my skills sharp.
This problem is supposedly from “erta to Offer”. My solution obviously has issues, but it still got accepted. I’ve realized that after writing PHP, JS, and C# for so long, I’ve almost forgotten how to use Vector.
The correct approach for this problem should be to use one stack to maintain the minimum value — push onto it whenever a new minimum is found. Another stack holds the data. This ensures O(n) complexity with O(1) query time.
My somewhat naive 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
41
42
43
| class MinStack {
private:
vector<int> stack;
int min;
public:
MinStack() {
stack.clear();
}
void push(int x) {
if (stack.empty() || min > x) {
min = x;
}
stack.push_back(x);
}
void pop() {
if (!stack.empty()) {
stack.pop_back();
genMin();
}
}
void genMin() {
min = *(stack.begin());
for (vector<int>::iterator i = stack.begin() + 1; i < stack.end(); i++) {
if (min > *i) {
min = *i;
}
}
}
int top() {
if (!stack.empty()) {
return *(stack.end() - 1);
}
return false;
}
int getMin() {
return min;
}
};
|