【題解】LeetCode 84. Largest Rectangle in Histogram

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int m = heights.size();
        if (m == 0) return 0;
        int a[m+2] = {};
        int ans = 0;
        stack <int> stk;
        stk.push(0);
        for (int i = 0; i < m; i++){
            a[i+1] = heights[i];
        }
        a[0] = -1;
        a[m+1] = -1;
        int l[m+2] = {}, r[m+2] = {};
        for (int j = 1; j <= m+1; j++){
            while(a[stk.top()] > a[j]){
                r[stk.top()] = j;
                stk.pop();
            }
            stk.push(j);
        }
        for (int j = m; j >= 0; j--){
            while(a[stk.top()] > a[j]){
                l[stk.top()] = j;
                stk.pop();
            }
            stk.push(j);
        }
        for (int j = 1; j <= m; j++){
            ans = max(ans, a[j]*(r[j]-l[j]-1));
        }
        return ans;
    }
};

class Solution {
public:
    int dc(vector<int>& heights, int s, int t) {
        //D&C, O(NlongN)
        if (s >= t) return 0;
        if (s+1 == t) return heights[s];
        //從中點分成左右兩半，考慮最大矩形落在其中一半
        int m = (s + t) / 2;
        int max_rect = max(dc(heights, s, m), dc(heights, m+1, t));
        //找出跨越中點的最大矩形面積，區間為[i+1, j-1]
        int i = m, j = m, h = heights[m], largest = 0;
        while (i >= s && j <= t) {
            //延伸左右範圍，逐步下降高度
            //考慮邊界條件
            if (i < s) h = heights[j];
            else if (j >= t) h = heights[i];
            else h = max(heights[i], heights[j]);
            while (i >= s && heights[i] >= h) {
                i--;
            }
            while (j < t && heights[j] >= h) {
                j++;
            }
            largest = max(largest, (j - i - 1) * h);
        }
        return max(max_rect, largest);
    }
    
    int largestRectangleArea(vector<int>& heights) {
        return dc(heights, 0, (int)heights.size());
    }
};