online advertising

Saturday, July 18, 2015

LeetCode OJ - Min Stack

Problem:

Please find the problem here.

Solution:

If getMin() has to be $ O(1) $, then we have to have the answer handy when we need. The simplest approach is to simply keep the current minimum with a stack element!

Code:

#include "stdafx.h"

// https://leetcode.com/problems/min-stack/

#include "LEET_MIN_STACK.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <stack>
#include <algorithm>

using namespace std;

namespace _LEET_MIN_STACK
{
    class MinStack
    {
    private:
        stack<int> val_stack;
        stack<int> min_stack;
    public:
        void push(int x)
        {
            int minimum = val_stack.empty() ? x : min(x, this->getMin());
            val_stack.push(x);
            min_stack.push(minimum);
        }

        void pop()
        {
            val_stack.pop();
            min_stack.pop();
        }

        int top()
        {
            return val_stack.top();
        }

        int getMin()
        {
            return min_stack.top();
        }
    };
};

using namespace _LEET_MIN_STACK;

int LEET_MIN_STACK()
{
    MinStack s;
    s.push(2);
    s.push(0);
    s.push(3);
    s.push(0);
    cout << s.getMin() << endl;
    s.pop();
    cout << s.getMin() << endl;
    s.pop();
    cout << s.getMin() << endl;
    s.pop();
    cout << s.getMin() << endl;
    return 0;
}

No comments :

Post a Comment