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

原问题链接：https://leetcode.com/problems/largest-rectangle-in-histogram/

 

问题分析

递归法

 

　　这个问题相对比较难想到一个比较好的思路。对于一个给定的柱状图来说，如果要求它所涵盖的最大矩形面积，那么它应该是一个在某个区域范围内的极小值乘以这个区域的长度。在一些极端的情况下也可能是单独的一个元素。那么，怎么来总结出这个关系来呢？

　　在一个给定的柱状图里给定的范围内，如果找到了一个极值点，那么这个区域内可能构成的最大矩形面积可能是这么几种情况：

　　１．区域长度乘以这个极值点。相当于是这个极值点虽然值不大，但是涵盖的范围比较广。

　　２．极值点左边的区域，包含这个极值点的范围。这种情况相当于存在于极值点左边的区域，但是不一定就和这个极值点相连。

　　３．极值点右边的区域，和上面的情况类似。

　　根据上述的讨论，这就形成了一个递归的关系。同时，在找到某个区域的极小值之后，这个极小值就将成为下一步递归划分的点。按照这个思路得到的递归关系其实比较简单。就是一个不断划分和比较返回结果的过程。

　　按照上述的讨论，我们可以得到一个如下的代码：

public class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) return 0;
        return getMax(heights, 0, heights.length);
    }
    
    int getMax(int[] heights, int s, int e) {
        if (s + 1 >= e) return heights[s];
        int min = s;
        for (int i = s; i < e; i++) {
            if (heights[min] > heights[i]) min = i;
        }
        int left = (min > s) ? getMax(heights, s, min) : 0;
        int right = (min < e - 1) ? getMax(heights, min + 1, e) : 0;
        return Math.max(Math.max(left, right), (e - s) * heights[min]);
    }
}

 　实际上，在数据相对比较大的时候，上述的代码执行速度很慢，基本上不能符合期望的要求。因为这里要不断的递归到最终只剩下单独的一个元素为止。如果要改进上述代码的性能的话，很可能需要从递归调用的深度改进开始。实际上代码里有一个可以改进的地方。就是当我们碰到的某个串它本身是递增的时候，我们求这个串里最大的覆盖矩阵面积就是通过从每个元素开始，用这个元素的值乘以从这个元素到末尾的距离，然后去最大的那个。通过这一步可以极大的加快程序执行，也缩小了递归需要调用的范围。

　　通过这种改进之后，我们得到的代码如下：

 

public class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) return 0;
        return getMax(heights, 0, heights.length);
    }
    
    int getMax(int[] heights, int s, int e) {
        if (s + 1 >= e) return heights[s];
        int min = s;
        boolean sorted = true;
        for (int i = s; i < e; i++) {
            if (i > s && heights[i] < heights[i - 1]) sorted = false;
            if (heights[min] > heights[i]) min = i;
        }
        if (sorted) {
            int max = 0;
            for (int i = s; i < e; i++) {
                max = Math.max(max, heights[i] * (e - i));
            }
            return max;
        }
        int left = (min > s) ? getMax(heights, s, min) : 0;
        int right = (min < e - 1) ? getMax(heights, min + 1, e) : 0;
        return Math.max(Math.max(left, right), (e - s) * heights[min]);
    }
}

 　因为这里缩减了递归调用的深度，程序执行的效率大大的提升了。

 

回溯法

　　这个方法和上面的过程有点不同，在一个柱状图中，它里面一个范围内的元素值可能是递增的，也可能是递减的。和前面求一个递增序列里面积的最大值相反，我们假设在某个点的时候碰到一个元素，它的值比前面的值要小，那么它可能涵盖的值范围则如下图：

　图中红线的部分表示所涵盖的行长度，在这里就有３中可能涵盖的面积需要进行计算。在实际的实现中，并不是整个图里的元素都是严格按照某个递增或者递减的顺序排列的，它可能是某一部分递增的，某一部分是递减的。它们的分布情况更可能像如下图的情况：

　　在这里，对于图中间极小值所分割的点来说，它右边的那些元素如果要求覆盖面积的话是不可能涵盖到这个极小值点的左边的。也就是说这个极小值起到了一个分割的作用。

　　到这里，我们可能就有了这么一个思路，就是用一个栈来保存到当前位置的极小值的索引。每次碰到的元素都和这个当前的极小值比较，如果这个值比极小值要小，那么我们就需要按照前面计算递减序列面积里的方法。每次判断当前值heights[i]，以及height[i] * i到当前极小值之间的距离。

　　在前面也提到，因为有可能出现有一个极小值在两段序列中间。后面有一段又是递增的。那么对于这个递增的序列来说，它相当于对应一个新的段里要计算的极小值了，需要将它加入到栈中间。因为这种情况的限制，我们需要比较的不仅仅是当前栈顶的元素，还需要和栈里面的元素比较，保证当栈中间的元素索引j满足heights[j] > i的情况，我们也必须要计算。

　　按照这种思路，代码的详细实现如下:

 

public class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length < 1)
            return 0;
        int[] stack = new int[heights.length + 1];
        int len = 0, max = 0;
        for (int i = 0; i <= heights.length; i++) {
            int h = (i == heights.length) ? 0 : heights[i];
            while (len != 0 && (i == heights.length || heights[stack[len - 1]] > h)) {
                if (len == 1)
                    max = Math.max(heights[stack[--len]] * i, max);
                else
                    max = Math.max(heights[stack[--len]] * (i - stack[len - 1] - 1), max);
            }
            stack[len++] = i;
        }
        return max;
    }
}

 

 

参考材料

 https://leetcode.com/discuss/91902/share-my-2ms-java-solution-beats-100%25-java-submissions