forked from haoel/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathminStack.cpp
More file actions
208 lines (181 loc) · 5.11 KB
/
minStack.cpp
File metadata and controls
208 lines (181 loc) · 5.11 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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
// Source : https://oj.leetcode.com/problems/min-stack/
// Author : Hao Chen
// Date : 2014-11-16
/**********************************************************************************
*
* Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
*
* push(x) -- Push element x onto stack.
*
* pop() -- Removes the element on top of the stack.
*
* top() -- Get the top element.
*
* getMin() -- Retrieve the minimum element in the stack.
*
*
**********************************************************************************/
#include <stdlib.h>
#include <iostream>
using namespace std;
//It seems C++ vector cause the Memory Limit Error, So, implement a simple one
template <typename T>
class Stack {
private:
T* _stack;
int _capacity;
int _top;
public:
Stack():_capacity(1),_top(-1){
_stack = (T*)malloc(_capacity*sizeof(T));
}
~Stack(){
free(_stack);
}
void push(T x){
_top++;
if ( _top >= _capacity ){
//if capacity is not enough, enlarge it 5 times.
//Notes: why 5 times? because if you change to other(e.g. 2 times),
// LeetCode system will report Run-time Error! it sucks!
_capacity*=5;
_stack = (T*)realloc(_stack, _capacity*sizeof(T));
}
_stack[_top] = x;
}
T pop() {
return top(true);
}
T& top(bool pop=false) {
if (_top>=0){
if (pop){
return _stack[_top--];
}
return _stack[_top];
}
static T null;
return null;
}
bool empty(){
return (_top<0);
}
int size() {
return _top+1;
}
void clear(){
_top = -1;
}
};
/*
* Idea:
*
* Using two stacks,
* 1) one stack is the real stack to store the data.
* 2) another stack store the minimal number when it changes.
*
* For example:
*
* if we keep pushing the following numbers:
* 5 1 1 2 3 2
* the minial number stack will be:
* 5 1 1 <-- only store the number which <= cureent minimal number
*
* Then, when we pop up the stack.
*
* we need compare whether the current number is the current minial number.
* if it is, then we need popup the number in minimal number stack.
*
*/
class MinStack {
private:
//Using a minData struct to remove the duplication in minimal stack
//which can save the memory.
struct minData{
int min;
int cnt;
minData():min(0), cnt(0) {}
minData(int m, int c):min(m),cnt(c){}
};
Stack<int> stack; //real stack store the data
Stack<minData> minStack; //minimal number stack store the number
int min; //current minial number
public:
void push(int x) {
if(stack.empty()){
min = x;
minStack.push(minData(x,1));
}else{
if (min >= x ){
min = x;
//if current minial number already pushed, then just add the reference coount.
if (minStack.top().min == x){
minStack.top().cnt++;
}else{
minStack.push(minData(x,1));
}
}
}
stack.push(x);
}
void pop() {
if (stack.empty()){
return;
}
int x = stack.pop();
if (x == minStack.top().min){
//de-reference the count at first.
if (minStack.top().cnt > 1){
minStack.top().cnt--;
}else{
minStack.pop();
min = minStack.top().min;
}
}
}
int top() {
return stack.top();
}
int getMin() {
return min;
}
void clear() {
stack.clear();
minStack.clear();
}
};
int main()
{
cout << "--- expected output [0, 0, 0, 2]" << endl;
MinStack ms;
ms.push(2);
ms.push(0);
ms.push(3);
ms.push(0);
cout << ms.getMin() << endl;
ms.pop();
cout << ms.getMin() << endl;
ms.pop();
cout << ms.getMin() << endl;
ms.pop();
cout << ms.getMin() << endl;
ms.clear();
cout << "--- expected output [2147483647 2147483646 2147483646 2147483647 2147483647 -2147483648 -2147483648 2147483647 " << endl;
ms.push(2147483646);
ms.push(2147483646);
ms.push(2147483647);
cout << ms.top() << endl;
ms.pop();
cout << ms.getMin() << endl;
ms.pop();
cout << ms.getMin() << endl;
ms.pop();
ms.push(2147483647);
cout << ms.top() << endl;
cout << ms.getMin() << endl;
ms.push(-2147483648);
cout << ms.top() << endl;
cout << ms.getMin() << endl;
ms.pop();
cout << ms.getMin() << endl;
return 0;
}