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

[balabala]  

方法1： O(N^2)  处理高度数组中每个元素时，左右分别找到第一个比当前高度低的位置，分别记为left, right, 则right - left - 1就是当前高度能围成的最大矩形的宽度，据此算出面积并更新全局最大面积值。

方法2：O(N) 使用stack 保存到当前位置处的高度非递减索引值，遇到一个高度比栈顶位置低的位置 i 时暂停下来，说明 i 是stack 中那些高于位置i 的bar的右边界，正是时候停下来计算那些高度对应的矩形面积。因为stack中是非递减序列，pop直到栈顶位置的高度小于某个正在计算的高度，pop结束时的位置就是正在计算的bar 的左边界。实现有两个方式，方式1 （method2）计算每个位置到右边界围成的面积，遇到等值大数组的case会超时，方式2（method3）pop直到找出左边界时才停下来计算，在遇到等值大数组时可节约可观的计算量。

重做该题时写了method4，原意是想节省method2中的copy数组开辟的额外空间，但遇到等值大数组时超时，在eclipse中调试，打印两个for循环耗时，input是长度为300000值均为1的数组，各方法耗时情况如下：

方法	耗时
method2	74ms
method3	28ms
method4	46ms(30+ 16)
method5	34ms(19 + 14)
method6	24ms

 

method5在method4基础上调整代码写法，去除一个多余的循环体，性能得到明显提升，让我大开眼界，不过仍然无法通过leetcode中的大case。另外通过比较method5和method3也可以看出构造一个for循环本身是有比较大的开销的。所以以后coding时要避免写不必要的循环体。比较method6 和method3, method6是以空间换时间，新开多一个元素的数组，最后一个元素是整个数组的最小值，以保证前面每个高度组成的矩形都得到计算，换句话说是替换外层循环体中的!stack.isEmpty()作用，节省了while循环和循环中if中的判断计算量。

[ref] http://www.cnblogs.com/lichen782/p/leetcode_Largest_Rectangle_in_Histogram.html

 

    // method 1
    public int largestRectangleArea(int[] height) {
        if (height == null)
            return 0;
        int n = height.length;
        int max = 0;
        for (int i = 0; i < n; i++) {
            int j = i - 1;
            while (j >= 0 && height[j] >= height[i]) {
                j--;
            }
            int left = i - j;
            j = i + 1;
            while (j < n && height[j] >= height[i]) {
                j++;
            }
            int right = j - i;
            max = Math.max(max, (left + right - 1) * height[i]);
        }
        return max;
    }

    // method 2
    public int largestRectangleArea(int[] height) {
        LinkedList<Integer> stack = new LinkedList<Integer>();
        int[] h = new int[height.length + 1];
        h = Arrays.copyOf(height, h.length);
        int i = 0;
        int max = 0;
        while (i < h.length) {
            if (stack.isEmpty() || h[i] >= h[stack.peek()]) {
                stack.push(i++);
            } else {
                int currH = h[stack.pop()];
                max = Math.max(max, currH * (stack.isEmpty() ? i : (i - stack.peek() - 1)));
            }
        }
        return max;
    }

    // method 3
    public int largestRectangleArea(int[] height) {
        LinkedList<Integer> stack = new LinkedList<Integer>();
        
        int max = 0;
        int i = 0;
        
        while(i < height.length || !stack.isEmpty()){
            if(stack.isEmpty() || i < height.length && height[i] >= height[stack.peek()]){
                stack.push(i++);
            }else{
                int currH = height[stack.pop()];
                while(!stack.isEmpty() && height[stack.peek()] == currH)
                    stack.pop();
                int left = stack.isEmpty() ? -1 : stack.peek();
                max = Math.max(max, currH * (i - left - 1));
            }
        }
        
        return max;
    }
    
    // method 4
    public int largestRectangleArea4(int[] height) {
        
        if (height == null || height.length == 0)
            return 0;
        int max = 0;
        LinkedList<Integer> stack = new LinkedList<Integer>();
        
        long start = System.currentTimeMillis();
        for (int i = 0; i < height.length; i++) {
            if (stack.isEmpty() || height[i] >= height[stack.peek()]) {
                stack.push(i);
            } else {
                while (!stack.isEmpty() && height[i] <height[stack.peek()]) {
                    int curr = stack.pop();
                    while (!stack.isEmpty() && height[curr] == height[stack.peek()]) {
                        stack.pop();
                    }
                    int width = stack.isEmpty() ? i : (i - stack.peek() - 1);
                    max = Math.max(max, height[curr] * width);
                }
                stack.push(i);
            }
        }
        System.out.println("part1=" + (System.currentTimeMillis() - start));
        start = System.currentTimeMillis();
        int rightBound = height.length;
        while (!stack.isEmpty()) {
            int curr = stack.pop();
            while (!stack.isEmpty() && height[curr] == height[stack.peek()]) {
                stack.pop();
            }
            int width = stack.isEmpty() ? rightBound : (rightBound - stack.peek() - 1);
            max = Math.max(max, height[curr] * width);
        }
        System.out.println("part2=" + (System.currentTimeMillis() - start));
        
        return max;
    }
    
 // method 5
    public int largestRectangleArea5(int[] height) {
        
        if (height == null || height.length == 0)
            return 0;
        int max = 0;
        LinkedList<Integer> stack = new LinkedList<Integer>();
        
        long start = System.currentTimeMillis();
        int i = 0;
        while(i < height.length) {
            if (stack.isEmpty() || height[i] >= height[stack.peek()]) {
                stack.push(i++);
            } else {
                int curr = stack.pop();
                while (!stack.isEmpty() && height[curr] == height[stack.peek()]) {
                    stack.pop();
                }
                int width = stack.isEmpty() ? i : (i - stack.peek() - 1);
                max = Math.max(max, height[curr] * width);
            }
        }
        System.out.println("part1=" + (System.currentTimeMillis() - start));
        start = System.currentTimeMillis();
        int rightBound = height.length;
        while (!stack.isEmpty()) {
            int curr = stack.pop();
            while (!stack.isEmpty() && height[curr] == height[stack.peek()]) {
                stack.pop();
            }
            int width = stack.isEmpty() ? rightBound : (rightBound - stack.peek() - 1);
            max = Math.max(max, height[curr] * width);
        }
        System.out.println("part2=" + (System.currentTimeMillis() - start));
        
        return max;
    }

    // method 6
    public int largestRectangleArea6(int[] h) {
        if (h == null || h.length == 0)
            return 0;
        int max = 0;
        int[] height = new int[h.length + 1];
        for (int i = 0; i < h.length; i++) {
            height[i] = h[i];
        }
        LinkedList<Integer> stack = new LinkedList<Integer>();
        
        for (int i = 0; i < height.length; i++) {
            if (stack.isEmpty() || height[i] >= height[stack.peek()]) {
                stack.push(i);
            } else {
                while (!stack.isEmpty() && height[i] <height[stack.peek()]) {
                    int curr = stack.pop();
                    while (!stack.isEmpty() && height[curr] == height[stack.peek()]) {
                        stack.pop();
                    }
                    int width = stack.isEmpty() ? i : (i - stack.peek() - 1);
                    max = Math.max(max, height[curr] * width);
                }
                stack.push(i);
            }
        }
        return max;
    }