[LeetCode] Largest Rectangle in Histogram

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,5,6,2,3],
return 10.

方法1:

这个方法会TLE！

O(n log n)，而且最快情况下，变成O(n^2).

之所以把这个写下来，是因为我蠢！

对于任意i～j， area = (j-i+1) * min(a[i]...a[j]);

因此在i~j内，如果要有更大的area，则必定需要去掉a[k] = min(a[i]...a[j]).

去掉a[k]后，则分成2段：i~k-1, k+1~j。则变成2个子问题。

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        if (height.size() == 0) return 0;
        return maxarea(&height[0], 0, height.size() - 1);
    }
    
    int maxarea(int* a, int start, int end) {
        if (start > end) return 0;
        if (start == end) return a[start];
        int minidx = start, minh = a[minidx];
        for (int i = start+1; i <= end; i++) {
            if (a[i] < minh) {
                minh = a[i];
                minidx = i;
            }
        }
        int tmp = (end - start + 1) * minh;
        int left = maxarea(a, start, minidx - 1);
        int right = maxarea(a, minidx + 1, end);
        int res = max(tmp, left);
        res = max(res, right);
        return res;
    }
};

方法2：

对于每一块板，找到left，right两边。离它最远的那个比不它矮的板。也就是等价于找到离他最近的那个比它矮的板a[k]。那么a[k-1]那块就是最远的不比他短的板。因为找到离他最近的比他矮的板，这是一个单调序列问题，可以O(N)处理。

所以分别O(N)处理left，right。

然后再O(N)扫一遍，对于每快以a[i]为最矮的矩形面积为maxarea[i] =  (right-left) * a[i];

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        int len = height.size();
        if (len == 0) return 0;
        vector<int> left(len, -1);
        vector<int> right(len, -1);
        left[0] = -1;
        stack<int> s;
        int *a = &height[0];
        for (int i = 0; i < len; i++) {
            while (!s.empty()) {
                if (a[s.top()] >= a[i]) s.pop();
                else break;
            }
            if (!s.empty()) left[i] = s.top();
            else left[i] = -1;
            s.push(i);
        }
        while(!s.empty()) s.pop();
        for (int i = len - 1; i >= 0; i--) {
            while (!s.empty()) {
                if (a[s.top()] >= a[i]) s.pop();
                else break;
            }
            if (!s.empty()) right[i] = s.top();
            else right[i] = len;
            s.push(i);
        }
        
        int res = -1;
        for (int i = 0; i < len; i++) {
            res = max(res, height[i]*(right[i] - left[i] - 1));
        }
        return res;
    
    }
};