#include <cassert>
#include <iostream>
class StackWithMin
{
int min;
int size;
int data[ 1024 ] ;
public :
StackWithMin& push ( int val ) {
if ( size == 0 ) {
data[ size] = val;
min = val;
} else if ( val < min) {
data[ size] = 2 * val - min;
min = val;
assert ( data[ size] < min) ;
} else {
data[ size] = val;
}
++ size;
// check size and grow array
return * this ;
}
int getMin ( ) {
return min;
}
int pop ( ) {
-- size;
int val = data[ size] ;
if ( ( size > 0 ) && ( val < min ) ) {
int prevMin = min;
min + = min - val;
return prevMin;
} else {
return val;
}
}
bool isEmpty ( ) {
return size == 0 ;
}
} ;
int main ( ) {
StackWithMin stack;
stack.push ( 10 ) .push ( 3 ) .push ( 6 ) .push ( 12 ) .push ( 2 ) .push ( 6 ) .push ( 9 ) .push ( 1 ) ;
while ( ! stack.isEmpty ( ) ) {
int min = stack.getMin ( ) ;
int val = stack.pop ( ) ;
std:: cout << "popped " << val << ", min " << min << "->"
<< stack.getMin ( ) << '\n ' ;
}
}
I2luY2x1ZGUgPGNhc3NlcnQ+CiNpbmNsdWRlIDxpb3N0cmVhbT4KCmNsYXNzIFN0YWNrV2l0aE1pbgp7CiAgICBpbnQgbWluOwogICAgaW50IHNpemU7CiAgICBpbnQgZGF0YVsxMDI0XTsKCiAgcHVibGljOgogICAgU3RhY2tXaXRoTWluJiBwdXNoICggaW50IHZhbCApIHsKICAgICAgICBpZiAoIHNpemUgPT0gMCApIHsKICAgICAgICAgICAgZGF0YVtzaXplXSA9IHZhbDsKICAgICAgICAgICAgbWluID0gdmFsOwogICAgICAgIH0gZWxzZSBpZiAoIHZhbCA8IG1pbikgewogICAgICAgICAgICBkYXRhW3NpemVdID0gMiAqIHZhbCAtIG1pbjsKICAgICAgICAgICAgbWluID0gdmFsOwoKICAgICAgICAgICAgYXNzZXJ0IChkYXRhW3NpemVdIDwgbWluKTsgCiAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgZGF0YVtzaXplXSA9IHZhbDsKICAgICAgICB9CgogICAgICAgICsrc2l6ZTsKCiAgICAgICAgLy8gY2hlY2sgc2l6ZSBhbmQgZ3JvdyBhcnJheQogICAgICAgIHJldHVybiAqdGhpczsKICAgIH0KCiAgICBpbnQgZ2V0TWluICgpIHsKICAgICAgICByZXR1cm4gbWluOwogICAgfQoKICAgIGludCBwb3AgKCkgewogICAgICAgIC0tc2l6ZTsKCiAgICAgICAgaW50IHZhbCA9IGRhdGFbc2l6ZV07CgogICAgICAgIGlmICggKCBzaXplID4gMCApICYmICggdmFsIDwgbWluICkgKSB7CiAgICAgICAgICAgIGludCBwcmV2TWluID0gbWluOwogICAgICAgICAgICBtaW4gKz0gbWluIC0gdmFsOwogICAgICAgICAgICByZXR1cm4gcHJldk1pbjsKICAgICAgICB9IGVsc2UgewogICAgICAgICAgICByZXR1cm4gdmFsOwogICAgICAgIH0KICAgIH0KCiAgICBib29sIGlzRW1wdHkgKCkgewogICAgICAgIHJldHVybiBzaXplID09IDA7CiAgICB9Cn07CgppbnQgbWFpbiAoKSB7CiAgICBTdGFja1dpdGhNaW4gc3RhY2s7CgogICAgc3RhY2sucHVzaCgxMCkucHVzaCgzKS5wdXNoKDYpLnB1c2goMTIpLnB1c2goMikucHVzaCg2KS5wdXNoKDkpLnB1c2goMSk7CgogICAgd2hpbGUgKCAhIHN0YWNrLmlzRW1wdHkoKSApIHsKICAgICAgICBpbnQgbWluID0gc3RhY2suZ2V0TWluKCk7CiAgICAgICAgaW50IHZhbCA9IHN0YWNrLnBvcCgpOwogICAgICAgIHN0ZDo6Y291dCA8PCAicG9wcGVkICIgPDwgdmFsIDw8ICIsIG1pbiAiIDw8IG1pbiA8PCAiLT4iCiAgICAgICAgICAgIDw8IHN0YWNrLmdldE1pbigpIDw8ICdcbic7CiAgICB9Cn0=
stdout
popped 1, min 1->2
popped 9, min 2->2
popped 6, min 2->2
popped 2, min 2->3
popped 12, min 3->3
popped 6, min 3->3
popped 3, min 3->10
popped 10, min 10->10