Competitive_Programming/Interview_Bit/Stacks_and_Queues/Min_stack.cpp at master · Ravi-Maurya/Competitive_Programming · GitHub

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
stack<int> min_stack;
int minElem = INT_MAX;
MinStack::MinStack() {
    while(!min_stack.empty())
        min_stack.pop();
    minElem = INT_MAX;
}
void MinStack::push(int x) {
    if(min_stack.empty()){
        min_stack.push(x);
        minElem = x;
    }
    else{
        if(x>=minElem)
            min_stack.push(x);
        else{
            min_stack.push(2*x - minElem);
            minElem = x;
        }
    }
}

void MinStack::pop() {
    if(!min_stack.empty()){
        int y = min_stack.top();
        min_stack.pop();
        if(y<minElem){
            minElem = 2*minElem - y;
        }
    }
}

int MinStack::top() {
    if(min_stack.empty())
        return -1;
    int t = min_stack.top();
    return (t<minElem) ? minElem : t;
}

int MinStack::getMin() {
    if(min_stack.empty())
        return -1;
    return minElem;
}