C++ two methods : O(NlogN) and O(N)


  • 1
    X
    class Solution {
    public:
    	//O(NLogN) divide and conquer, 
    	//using segment tree to find range minmum
    	int getMin(vector<int>& hist, int i, int j) {
    		if (i == -1) return j;
    		if (j == -1) return i;
    		return (hist[i] < hist[j]) ? i : j;
    	}
    	int RMQUtil(vector<int>& hist, vector<int>& st, int ss, int se, int qs, int qe, int index)
    	{
    		if (se < qs || ss > qe) {
    			return -1;
    		}
    		else if (qs <= ss && qe >= se) {
    			return st[index];
    		}
    		int mid = ss + (se - ss) / 2;
    		int left = RMQUtil(hist, st, ss, mid, qs, qe, 2 * index + 1);
    		int right = RMQUtil(hist, st, mid + 1, se, qs, qe, 2 * index + 2);
    		return getMin(hist, left, right);
    	}
    	int constructSTUtil(vector<int>& hist, int ss, int se, vector<int>& st, int si)
    	{
    		if (ss == se) {
    			return (st[si] = ss);
    		}
    		int mid = ss + (se - ss) / 2;
    		int left = constructSTUtil(hist, ss, mid, st, si * 2 + 1);
    		int right = constructSTUtil(hist, mid + 1, se, st, si * 2 + 2);
    		st[si] = getMin(hist, left, right);
    		return st[si];
    	}
    	vector<int> constructST(vector<int>& hist, int n)
    	{
    		int x = (int)(ceil(log2(n)));
    		int max_size = 2 * (int)pow(2, x) - 1;
    		vector<int> st(max_size, 0);
    		constructSTUtil(hist, 0, n - 1, st, 0);
    		return st;
    	}
    	int recur(int left, int right, vector<int>& heights, vector<int>& st) {
    		if (left > right) {
    			return INT_MIN;
    		}
    		else if (left == right) {
    			return heights[left];
    		}
    
    		int minIdx = RMQUtil(heights, st, 0, heights.size() - 1, left, right, 0);
    		/* the linear search will cause TLE
    		int minValue = INT_MAX;
    		int minIdx = -1;
    		for(int i = left; i <= right; ++i){
    		if(heights[i] < minValue){
    		minValue = heights[i];
    		minIdx = i;
    		}
    		}*/
    		int leftMin = recur(left, minIdx - 1, heights, st);// it's max , the name is misleading, sorry
    		int rightMin = recur(minIdx + 1, right, heights, st);
    		return max(max(leftMin, rightMin), heights[minIdx] * (right - left + 1));
    
    	}
    	int largestRectangleArea(vector<int>& heights) {
    		int len = heights.size();
    		if (len == 0) {
    			return 0;
    		}
    		vector<int> st = constructST(heights, len);
    		return recur(0, len - 1, heights, st);
    	}
        //O(N) stack
        /*
        int largestRectangleArea(vector<int>& heights) {
            int ans = 0;
            int len = heights.size();
            if(len == 0){
                return 0;
            }
            stack<int> st;
            for(int i = 0; i <= len;){
                int h = (i == len ? 0 : heights[i]);
                if(st.empty() || heights[st.top()] <= h){
                    st.push(i++);
                }else{
                    int tmp = st.top();
                    st.pop();
                    int l = (st.empty() ? i : i - st.top() - 1);
                    ans = max(ans, l * heights[tmp]);
                }
            }
            return ans;
        }
        */
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.