LeetCode 84 Largest Rectangle in Histogram

Descriptin:

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.

---

题目理解：本题需要从柱状图中找出最大的长方形，求解当然不难，但是想要降低复杂度就很难。

---

代码一：

最简单的求解方法，遍历柱状图，对每一根柱，求它的最大长方形，所以也需要一个循环来做，于是复杂度O(n^2)。

class Solution {
    public int largestRectangleArea(int[] heights) {
        int max = 0, n = heights.length;
        for ( int i = 0; i < n; i++ ) {
            int left = i - 1, right = i + 1;
            while ( left >= 0 && heights[left] >= heights[i] )
                left--;
            while ( right < n && heights[right] >= heights[i] )
                right++;
            int area = (right - left - 1) * heights[i];
            if ( max < area )
                max = area;
        }
        return max;
    }
}

结果是代码超时，最后一个用例全是1，卡在上面了。

---

代码二：

这个代码是自己想了很久写出来的，看了别人的才发现自己有些地方想偏了，所以才想了这么久。

想法是，由于在上面遍历过程中，老是重复一些东西，所以这里对已经遍历过的部分进行一定的处理，并且计算方式有所变化。

遍历到一个柱时，它前面的柱体一定是削平了的。

如下图，

在遍历到下标3时，把前面变成2削成了1，同时下标1的1值也不用再保存了， 因为后面的柱体和它组成的长方形一定没有与前面的“1”大。

同样的，遍历到下标5时会变成下面的形式，

前面只是保证了前面的柱体是削平的，那么时候去计算长方形的大小呢？当遇到下坡时就去计算，

比如当遍历到2的时候，

它前面的柱体呈现一个1,5,6的形式，由于5,6比2高，那么就要去把它们削到高度为2， 在削的时候，就去计算被削的柱体它能组成的长方形大小。 比如高度为6的柱体，因为它是被削平的，所以它到当前高度2的柱体之间如果有别的柱体，也一定是至少比6要高的。 所以就长方形的长度就等于6到2之间的间隔，乘上6。

这样每一个柱体只会计算一次长方形的大小，并且这个过程是没有查找的操作的。

所以复杂度为O(n)。

class Solution {
    public int largestRectangleArea(int[] heights) {
        int max = 0, flen = 0, n = heights.length;
        int[][] front = new int[n][2];
        for ( int i = 0; i < n; i++ ) {
            if ( flen == 0 || heights[i] > front[flen-1][0] ) {
                front[flen][0] = heights[i];
                front[flen++][1] = i;
            } else {
                int j = flen - 1;
                while ( j >= 0 && front[j][0] > heights[i] ) {
                    int area = (i - front[j][1]) * front[j][0];
                    if ( area > max )
                        max = area;
                    j--;
                }
                if ( j == -1 || front[j][0] < heights[i] )
                    j++;
                front[j][0] = heights[i];
                flen = j + 1;
            }
        }
        int j = flen - 1;
        while ( j >= 0 ) {
            int area = (n - front[j][1]) * front[j][0];
            if ( area > max )
                max = area;
            j--;
        }
        return max;
    }
}

---

代码三：

这个是看的别人的代码，这个思想很好，而且正好是从代码一最简单形式变化而来的，不得不佩服。

考虑到代码一每次都重复去寻找左右比当前柱体矮的柱体，它就相当于进行了预处理，先将一个柱体的左右比它矮的柱体找到了， 然后就可以快速的计算了。

int[] lessFromLeft = new int[height.length];

for (int i = 1; i < height.length; i++) {
    int p = i - 1;

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

最重要的就是上面的代码，它就是去寻找当前柱体左边的第一个比它矮的柱体，使用了一个数组进行保存柱体下标， 它的核心思想是，前面的柱体已经找到了比自己矮的柱体的位置，那么当前柱体就可以利用到这个信息， 快速的找到比自己矮的柱体。就如写这个代码的那个人所说，这里的思想有点像KMP。

这里的这种将问题拆分，然后进行求解的思想值得学习。

private int largestRectangleArea(int[] heights) {
    if ( matrix == null || matrix.length == 0 ) return 0;
    int max = 0, n = heights.length;
    int[] small_left = new int[n];
    int[] small_right = new int[n];
    small_left[0] = -1;
    small_right[n-1] = n;
    for ( int i = 1; i < n; i++ ) {
        int idx = i - 1;
        while ( idx >= 0 && heights[idx] >= heights[i] )
            idx = small_left[idx];
        small_left[i] = idx;
    }
    for ( int i = n - 2; i >= 0; i-- ) {
        int idx = i + 1;
        while ( idx < n && heights[idx] >= heights[i] )
            idx = small_right[idx];
        small_right[i] = idx;
    }
    for ( int i = 0; i < n; i++ ) {
        int area = (small_right[i] - small_left[i] - 1) * heights[i];
        if ( area > max )
            max = area;
    }
    return max;
}

运行时间：5ms。
复杂度：O(n)。