Max Stack Solutions in C++

/// Source : https://leetcode.com/problems/max-stack/description/
/// Author : liuyubobobo
/// Time   : 2017-11-16

#include <iostream>
#include <set>
#include <cassert>

using namespace std;

/// Using two sets
/// Time Complexity: push: O(logn)
///                  pop:  O(logn)
///                  top:  O(logn)
///                  peekMax: O(logn)
///                  popMax:  O(logn)
/// Space Complexity: O(n)
class MaxStack {

private:
    int index = 0;
    set<pair<int, int>> vi;   // value - index
    set<pair<int, int>> iv;   // index - value

public:
    /** initialize your data structure here. */
    MaxStack() {
        vi.clear();
        iv.clear();
        index = 0;
    }

    void push(int x) {
        vi.insert(make_pair(x, index));
        iv.insert(make_pair(index, x));
        index ++;
    }

    int pop() {

        assert(iv.size() > 0);

        pair<int, int> e_iv = *iv.rbegin();
        iv.erase(e_iv);

        pair<int, int> e_vi = make_pair(e_iv.second, e_iv.first);
        vi.erase(e_vi);

        return e_iv.second;
    }

    int top() {
        assert(iv.size() > 0);
        return iv.rbegin()->second;
    }

    int peekMax() {
        assert(vi.size() > 0);
        return vi.rbegin()->first;
    }

    int popMax() {

        assert(vi.size() > 0);

        pair<int, int> e_vi = *vi.rbegin();
        vi.erase(e_vi);

        pair<int, int> e_iv = make_pair(e_vi.second, e_vi.first);
        iv.erase(e_iv);

        return e_vi.first;
    }
};


int main() {

    MaxStack stack;
    stack.push(5);
    stack.push(1);
    stack.push(5);
    cout << stack.top() << endl;     // -> 5
    cout << stack.popMax() << endl;  // -> 5
    cout << stack.top() << endl;     // -> 1
    cout << stack.peekMax() << endl; // -> 5
    cout << stack.pop() << endl;     // -> 1
    cout << stack.top() << endl;     // -> 5

    return 0;
}

/// Source : https://leetcode.com/problems/max-stack/description/
/// Author : liuyubobobo
/// Time   : 2017-11-27

#include <iostream>
#include <stack>
#include <cassert>

using namespace std;

/// Using two stacks
/// We have one regular stack for push, pop and top operations
/// We have another stack for peekMax and popMax operations, which named maxStack
/// maxStack will store the current max value in the stack
/// for popMax, we will find the max value in the stack in O(n) time
///
/// Time Complexity: push: O(1)
///                  pop:  O(1)
///                  top:  O(1)
///                  peekMax: O(1)
///                  popMax:  O(n)
/// Space Complexity: O(n)
class MaxStack {

private:
    stack<int> normalStack;
    stack<int> maxStack;

public:
    /** initialize your data structure here. */
    MaxStack() {
        while(!normalStack.empty())
            normalStack.pop();

        while(!maxStack.empty())
            maxStack.pop();
    }

    void push(int x) {
        normalStack.push(x);
        if(maxStack.empty())
            maxStack.push(x);
        else
            maxStack.push(max(maxStack.top(), x));
    }

    int pop() {

        assert(normalStack.size() > 0);

        int v = normalStack.top();
        normalStack.pop();
        maxStack.pop();

        return v;
    }

    int top() {
        assert(normalStack.size() > 0);
        return normalStack.top();
    }

    int peekMax() {
        assert(normalStack.size() > 0);
        return maxStack.top();
    }

    int popMax() {

        assert(normalStack.size() > 0);

        int maxValue = peekMax();
        stack<int> tstack;

        while(true){
            int value = pop();

            if(value == maxValue)
                break;

            tstack.push(value);
        }

        while(!tstack.empty()){
            push(tstack.top());
            tstack.pop();
        }

        return maxValue;
    }
};

int main() {

    MaxStack stack;
    stack.push(5);
    stack.push(1);
    stack.push(5);
    cout << stack.top() << endl;     // -> 5
    cout << stack.popMax() << endl;  // -> 5
    cout << stack.top() << endl;     // -> 1
    cout << stack.peekMax() << endl; // -> 5
    cout << stack.pop() << endl;     // -> 1
    cout << stack.top() << endl;     // -> 5

    return 0;
}

/// Source : https://leetcode.com/problems/max-stack/description/
/// Author : liuyubobobo
/// Time   : 2017-11-27

#include <iostream>
#include <map>
#include <cassert>
#include <list>
#include <vector>

using namespace std;

/// Using a list to simulate th stack
/// Using a TreeMap to record every node in the list
/// So we can get the max value in the list quickly and erase it easily
///
/// Time Complexity: push: O(1)
///                  pop:  O(1)
///                  top:  O(1)
///                  peekMax: O(1)
///                  popMax:  O(logn)
/// Space Complexity: O(n)
class MaxStack {

private:
    list<int> stack;
    map<int, vector<list<int>::iterator>> record;

public:
    /** initialize your data structure here. */
    MaxStack() {
        stack.clear();
        record.clear();
    }

    void push(int x) {
        stack.push_back(x);

        list<int>::iterator iter = stack.begin();
        advance(iter, stack.size() - 1);

        record[x].push_back(iter);
    }

    int pop() {

        int ret = stack.back();
        stack.pop_back();

        record[ret].pop_back();
        if(record[ret].size() == 0)
            record.erase(ret);

        return ret;
    }

    int top() {
        assert(stack.size() > 0);
        return stack.back();
    }

    int peekMax() {
        assert(stack.size() > 0);
        return record.rbegin()->first;
    }

    int popMax() {
        assert(stack.size() > 0);
        int ret = record.rbegin()->first;

        stack.erase((record.rbegin()->second).back());
        (record.rbegin()->second).pop_back();
        if((record.rbegin()->second).size() == 0)
            record.erase(ret);
        return ret;
    }
};


int main() {

    MaxStack stack1;
    stack1.push(5);
    stack1.push(1);
    stack1.push(5);
    cout << stack1.top() << endl;     // -> 5
    cout << stack1.popMax() << endl;  // -> 5
    cout << stack1.top() << endl;     // -> 1
    cout << stack1.peekMax() << endl; // -> 5
    cout << stack1.pop() << endl;     // -> 1
    cout << stack1.top() << endl;     // -> 5
    cout << endl;

    // ---

    MaxStack stack2;
    stack2.push(-83);
    stack2.push(-1);
    stack2.push(98);
    stack2.push(38);
    stack2.push(-99);
    cout << stack2.top() << endl;     // -> -99
    cout << stack2.popMax() << endl;  // -> 98
    cout << stack2.popMax() << endl;  // -> 38
    stack2.push(-92);
    stack2.push(-17);
    stack2.push(-1);
    stack2.push(-74);
    cout << stack2.popMax() << endl;  // -> -1
    cout << stack2.pop() << endl;     // -> -74
    cout << stack2.popMax() << endl;  // -> -1
    stack2.push(-80);
    stack2.push(-13);
    cout << stack2.top() << endl;     // -13
    stack2.push(-25);
    cout << endl;

    // ---

    MaxStack stack3;
    stack3.push(74);
    cout << stack3.popMax() << endl;  // -> 74
    stack3.push(89);
    stack3.push(67);
    cout << stack3.popMax() << endl;  // -> 89
    cout << stack3.pop() << endl;     // -> 67
    stack3.push(61);
    stack3.push(-77);
    cout << stack3.peekMax() << endl; // 61
    cout << stack3.popMax() << endl;  // 61
    stack3.push(81);
    cout << stack3.pop() << endl;     // 81
    stack3.push(-71);
    stack3.push(32);

    return 0;
}