FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
leetcode/algorithms/cpp/minStack/minStack.cpp at master · openhardnudd/leetcode · GitHub
openhardnudd
/
leetcode
Public
forked from
haoel/leetcode
Notifications
You must be signed in to change notification settings
Fork
0
Star
0
Code
Pull requests
0
Actions
Projects
Wiki
Security and quality
0
Insights
Additional navigation options
Code
Pull requests
Actions
Projects
Wiki
Security and quality
Insights
Expand file tree
Breadcrumbs
leetcode
/
algorithms
/
cpp
/
minStack
/
minStack.cpp
Copy path
More file actions
More file actions
Latest commit
History
History
History
208 lines (181 loc) · 5.11 KB
Breadcrumbs
leetcode
/
algorithms
/
cpp
/
minStack
/
minStack.cpp
Copy path
File metadata and controls
208 lines (181 loc) · 5.11 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
;
}
Back
|
FazBrowse Home
|
New Git URL