Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3]. The largest rectangle is shown in the shaded area, which has area = 10 unit. For example, Given height = [2,1…

Largest Rectangle in Histogram.cpp

class Solution {
private:
    vector<int> tmp;
public:
    int largestRectangleArea(vector<int> &height) {
        this->tmp = height;
        if(height.size() == 0) {
            return 0;
        }
        
        return cal(0, tmp.size());
    }
    
    int cal(int min, int max) {
        if(max - min == 1) {
            return tmp[min];
        }
        
        int mid = min + (max - min) / 2;
        
        int left = cal(min, mid);
        int right = cal(mid, max);
        
        int comb = MIN(tmp[mid - 1], tmp[mid]) * 2;
        int combRes = comb;
        int leftP = mid - 2;
        int rightP = mid + 1;
        int length = 2;
        while(leftP >= min or rightP < max) {
            int leftH = leftP >= min ? tmp[leftP] : -1;
            int rightH = rightP < max ? tmp[rightP] : -1;
            
            if(leftH > rightH) {
                --leftP;
                comb = MIN(comb / length, leftH) * (++length);
            } else {
                ++rightP;
                comb = MIN(comb / length, rightH) * (++length);
            }
            combRes = MAX(combRes, comb);
        }
        return MAX(combRes, MAX(left, right));
    }
    
    int MIN(int a, int b) {
        return min(a, b);
    }
    
    int MAX(int a, int b) {
        return max(a, b);
    }
};