# 84 - Largest Rectangle in Histogram

解法一 - 以每個柱子為高，看以哪個柱子為高的面積會最大

一開始會最容易想到的方法大概就是暴力法，看看每個柱子都當作高，各自形成的長方形面積會是多少，再選出一個最大的。實作如下：

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if(heights.empty()) return 0;

        int maxArea = INT_MIN;

        for(int i=0; i<heights.size(); i++) {
            int area = heights[i], l=i, r=i;
            bool lFlag = true, rFlag = true;

            while(lFlag || rFlag) {
                l--;
                if(l >= 0 && heights[l] >= heights[i] && lFlag) { 
                    area+=heights[i]; 
                }
                else { 
                    lFlag = false; 
                }

                r++;
                if(r < heights.size() && heights[r] >= heights[i] && rFlag) { 
                    area+=heights[i]; 
                }
                else { 
                    rFlag = false; 
                }
            }

            if(area > maxArea) maxArea = area;
        }

        return maxArea;
    }
};

這樣做是可行的，可惜只能過 95/96 test cases，最後一個會 TLE。

解法二 - 優化搜尋當前柱的左邊界跟右邊界

從解法一我們可以發現，往左找邊界跟往右找邊界的停止條件都是：

1. 遇到第一個比目前柱子矮的柱子

2. 超出邊界

所以如果有一個方法可以快速地找到左邊第一個小於當前柱的 index 跟右邊第一個小於當前柱的 index，就能節省計算時間。因為原本是對每個當前柱都得重新花一次 O(N) 時間搜尋，所以得花 $O(N^2)$ 來找，但我們其實可以運用之前已經看到的記錄，來推算當前柱的左邊界跟右邊界。

整體演算法的思想如下：

1. For each position i, we can calculate the area of the largest rectangle that contains i by find the first positions to its left and to its right with heights[l] < height[i] and heights[r]< height[i]; so maxArea = Math.max(maxArea, heights[i] * (r - l - 1));

2. In order to find l and r, the brute force method is to do a bidirectional scan start from i; the time cost will be O(n ^ 2);

3. The time complexity can be simplified to O(n):

   for example in order to left[i]; if height[i - 1] < height[i] then left[i] = i - 1; other wise we do not need to start scan from i - 1; we can start the scan from left[i - 1], because since left[i - 1] is the first position to the left of i - 1 that have height less than height[i - 1], and we know height[i - 1] >= height[i]; so left[i] must be at the left or at left[i - 1]; similar for the right array;

實作出來的程式碼是：

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if(heights.empty()) return 0;

        // Calculate lessFromLeft & lessFromRight
        int n = heights.size();
        vector<int> lessFromLeft(n);
        vector<int> lessFromRight(n);
        lessFromLeft[0] = -1;
        lessFromRight[n-1] = n;

        for(int i=1; i<n; i++) {
            int p = i-1;

            while(p>=0 && heights[p] >= heights[i])
                p = lessFromLeft[p];
            lessFromLeft[i] = p;
        }

        for(int i=n-2; i>=0; i--) {
            int p = i+1;

            while(p<n && heights[p] >= heights[i])
                p = lessFromRight[p];
            lessFromRight[i] = p;
        }

        // Calculate maxArea
        int maxArea = INT_MIN;

        for(int i=0; i<n; i++) {
            int area = heights[i] * (lessFromRight[i] - lessFromLeft[i] - 1);
            maxArea = max(maxArea, area);
        }

        return maxArea;
    }
};