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.

Example:

Input: [2,1,5,6,2,3]
Output: 10

解析

此題給予一組非負整數代表一組直方圖的高度，每個間距皆為一，要求直方圖所組成的最大矩形。難度為Hard。

因為兩個長條之間所能組成的最大矩形取決於這兩個長條之間的最小高度，所以可用暴力法從第一個長條開始依序算出所有其與後面長條所能形成的矩形面積，其最大值即為所求。

時間複雜度更低的方法是分而治之法(Divide and Conquer)，因為最大面積不外乎下列三者之一：

• 最小高度乘以全長
• 最小高度左側的最大面積（不包括最小高度）
• 最小高度右側的最大面積（不包括最小高度）

所以若能先找出直方圖中的最小高度，算出該短板所能圍出的最大面積，接著遞迴地以該短板為中心點，分別算出其右邊與左邊分別能圍出的最大面積，則此三者間的最大值即為所求。

解法一(Brute Force)

時間複雜度：O(N^2)
空間複雜度：O(N)

 public class Solution {
    public int largestRectangleArea(int[] heights) {
        int maxarea = 0;
        int bars = heights.length;
        for (int i = 0; i < bars; i++) {
            int minheight = Integer.MAX_VALUE;
            for (int j = i; j < bars; j++) {
                minheight = Math.min(minheight, heights[j]);
                maxarea = Math.max(maxarea, minheight * (j - i + 1));
            }
        }
        return maxarea;
    }
}

解法二(Divide and Conquer)

時間複雜度：O(NlogN)
空間複雜度：O(N)

public class Solution {
    public int calculateArea(int[] heights, int start, int end) {
        if (start > end) {
            return 0;
        }
        int minindex = start;
        for (int i = start; i <= end; i++)
            if (heights[minindex] > heights[i])
                minindex = i;
        return Math.max(heights[minindex] * (end - start + 1), Math.max(calculateArea(heights, start, minindex - 1), calculateArea(heights, minindex + 1, end)));
    }
    public int largestRectangleArea(int[] heights) {
        return calculateArea(heights, 0, heights.length - 1);
    }
}

備註

希望透過記錄解題的過程，可以對於資料結構及演算法等有更深一層的想法。
如有需訂正的地方歡迎告知，若有更好的解法也歡迎留言，謝謝。