NO CODING NO LIFE: LeetCode: Min Stack

There are two ways to record min:
1. with a stack. When pop an element in data, just check the last element in min stack. O(1);
2. with a variable. When pop an element in data, need to reiterate elements in data to get the min value. O(n)

class MinStack {
public:
    vector<int> data;
    vector<int> min;
    void push(int x) {
        data.push_back(x);
        /*
        if(min.empty()) {
            min.push_back(x);
            return;
        }
        if(x<=min.back()) min.push_back(x);*/
        //optimize
        if(min.empty() || min.back()>=x) 
            min.push_back(x);
    }
    void pop() {
        if(data.back() == min.back()) min.pop_back();
        data.pop_back();
    }
    int top() {
        return data.back();
    }

    int getMin() {
        return min.back();
    }
};

Here is a trick: stack just stores the difference of current element to previous minimum element. set a variable to store the minimum vanlue. Then we can realize O(1) to get minimum value with just one variable

push():
we need to get the minimum value before x is added
this is in two cases:
when the data is empty, minimum=input
when data is not empty, min now is the minimum value before the current back() element. So we need to compare min and the current back() element to get the min including back() value.

pop():
when pop the last element, for the previous element, the min may change, so we need to update the min value to pmin.
only when(p<pmin) min=p;
otherwise min=pmin.

Now p=pmin+pd(the data stored for p in stack);
p<pmin ==> pmin+pd<pmin ==> pd<0;
min=p ==> min=pmin+pd ==> pmin=min-pd

SO the condition becomes:
only when(pd<0) pmin=min-pd
otherwise pmin=min.

Then it's easy to update min to pmin.

Draw will help.
---------------------min--------
-------pmin---- |
| |
| |
xx x | p | last element in stack

class MinStack {
public:
    vector<int> data;
    int min;
    void push(int x) {
        //get the minimum value before x is added
        if(data.empty()) {
            min=x;
        }
        else{
            int prev=data.back()+min; //prev is the last value stored
            if(prev < min) min=prev;
        }
        data.push_back(x-min);
    }
    void pop() {
        data.pop_back();
        if(data.back()<0) min=min-data.back();
    }
    int top() {
        return data.back()+min;
    }
    int getMin() {
        return (top()<min)?top():min;
    }
};

Reference:
http://yucoding.blogspot.com/2014/12/leetcode-question-min-stack.html
http://blog.csdn.net/u010367506/article/details/41045797 //explain the trick way

NO CODING NO LIFE

2015年7月6日星期一

LeetCode: Min Stack

没有评论:

发表评论