LeetCode Min Stack

Description

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.

The original problem is here.

The original code is here.

My Solution

I solve this problem in C++, as below:

/*
*Min Stack 
*Author: shuaijiang
*Email: zhaoshuaijiang8@gmail.com
*/
#include<iostream>
#include<vector>
#include<stdlib.h>
using namespace std;

class MinStack {
public:
    vector<int> stack;
    vector<int> minStack;
    vector<int>::iterator iter, minIter;
    vector<int>::reverse_iterator reiter;
    void push(int x) {
        stack.push_back(x);
        if(minStack.size()<1)
            minStack.push_back(x);
        else{
            reiter = minStack.rbegin();
            if(x <= *reiter)
                minStack.push_back(x);
        }
    }

    void pop() {
        if(stack.size() < 1)
            return ; 
        reiter = stack.rbegin();
        int num = * reiter;
        reiter = minStack.rbegin();
        int minNum = *reiter;
        
        stack.pop_back();
        if(num == minNum){
            minStack.pop_back();
        }
    }

    int top() {
        reiter = stack.rbegin();
        return *reiter;
    }

    int getMin() {
        reiter = minStack.rbegin();
        return *reiter;
    }
};

Note

The operations of stack are easy but the getMin, we need create another stack to save the minimum value.