Largest Rectangle in Histogram

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.

Naive Way: brute force的方法，对于每一个长方形都追溯两头，直到小于它，这样就是O(n^2)，很明显，冗余在于如果之前经过这个长方形，那么下一次就已经有了信息，不用再经过了，所以应该O(n)就可以。

我想到一个方法，需要两次遍历。第一次先往后找第一个小于当前数值的位置，如果下一个碰不到，说明下一个比当前大，就先找下一个的，一旦找到就记下位置，这样需要一个stack来记入之前空着的没找到下一个的那些index。然后从后往前来一遍找在它前面的数值小于它的位置。

算法复杂度为O(n)。 这个方法和GeeksforGeeks中的方法是一样的，但是这个更冗余些。

public class Solution {
    public int largestRectangleArea(int[] height) {
        int forward[] = new int[height.length];
        int backward[] = new int[height.length];
        int largest = 0;
        int i;
        for(i = 0;i < forward.length;i++) forward[i] = forward.length;
        for(i = 0;i < backward.length;i++) backward[i] = -1;
        Stack<Integer> stack = new Stack<Integer>();
        // forward
        i = 0;
        while(i < height.length){
            if(!stack.isEmpty() && height[i] < height[stack.peek()])
                forward[stack.pop()] = i;
            else
                stack.push(i++);
        }
        // backward
        stack.clear();
        i = height.length-1;
        while(i >=0){
            if(!stack.isEmpty() && height[i] < height[stack.peek()])
                backward[stack.pop()] = i;
            else
                stack.push(i--);
        }
        // generate result
        for(i =0;i < height.length;i++) largest = Math.max(largest, height[i]*(forward[i]-backward[i]-1));
        return largest;
    }
}

 

Improved Way: 仅通过这个stack能否同时知道forward和backward的位置呢。看了GeeksforGeeks的方法后，知道了如何用一个stack同时track两边的情况，关键就是要把一些index留在stack里，就是forward的遍历一遍以后，那么没有找到右边比自己小的数的位置，就留在了stack里面，这些位置的左边的比自己小的数就可以根据留在stack里的数确定，因为如果比它大，就会在forward遍历的时候被推出。

 

public class Solution {
    public int largestRectangleArea(int[] height) {
        int largest = 0;
        int i;
        Stack<Integer> stack = new Stack<Integer>();
        // forward
        i = 0;
        while(i < height.length){
            if(!stack.isEmpty() && height[i] < height[stack.peek()])
                largest = Math.max(largest, height[stack.pop()]*(i-(stack.isEmpty()?-1:stack.peek())-1));
            else
                stack.push(i++);
        }
        // backward
        while(!stack.isEmpty()){
            largest = Math.max(largest, height[stack.pop()] * (i-(stack.isEmpty()?-1:stack.peek())-1));
        }
        return largest;
    }
}

 

最后的感觉就是这事一道强化版的Longest Valid Parentheses 。这里变成了相同大小的数是匹配对。

然后再Discuss里还看到有一种Divide&Conquer的做法，算法复杂度是O(nlogn)，我觉得应该不是比较理想的做法。呼声最高的是https://oj.leetcode.com/discuss/22147/simple-divide-and-conquer-ac-solution-without-segment-tree。