84. Largest Rectangle in Histogram

melody_lql 發(fā)布于2019-08-14 18:01 / 3458人閱讀

摘要：要求一個(gè)矩形的面積，要知道高和寬。如果每次確定高度為然后調(diào)用一個(gè)找到左右邊界，即不小于的最左和最右。這是一個(gè)明顯的算法，每次掃描都會(huì)重走整個(gè)。一個(gè)遞增序列這種，我們知道可以夠成的矩形是會(huì)不斷增大的。遞增序列預(yù)處理，遞減的時(shí)候計(jì)算。

For example,
Given heights = [2,1,5,6,2,3],
return 10

要求一個(gè)矩形的面積，要知道高和寬。
如果每次確定高度為height[i], 然后調(diào)用一個(gè)helper function找到左右邊界，即不小于height[i]的最左和最右。
這是一個(gè)明顯O(N^2)的算法，每次掃描都會(huì)重走整個(gè)array。
這里有些步驟是不必要的，比如高度為2往左掃的時(shí)候已經(jīng)知道2>1了，然當(dāng)高度為1的時(shí)候，不必往左走，我們可以通過空間來記憶已知信息。
一個(gè)遞增序列156這種，我們知道可以夠成的矩形是會(huì)不斷增大的。而當(dāng)1562,遇到2的時(shí)候矩形可能變小，這時(shí)我們就要計(jì)算面積了。
遞增序列預(yù)處理，遞減的時(shí)候計(jì)算。

用代碼打印出每步的結(jié)果。
height : 0 left :0 right : 1 cur 2 area : 2
height : 3 left :3 right : 4 cur 6 area : 6
height : 2 left :2 right : 4 cur 10 area : 10
height : 5 left :5 right : 6 cur 3 area : 10
height : 4 left :2 right : 6 cur 8 area : 10
height : 1 left :0 right : 6 cur 6 area : 10

public class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack stk = new Stack<>();
        int area = 0;
        for(int i=0; i<= heights.length; i++){
            int h = i == heights.length ? 0 : heights[i];
            if(stk.isEmpty() || h >= heights[stk.peek()]){
                stk.push(i);
            } else {
                int top = stk.pop();
                // 為什么用stk.peek()+1, 因?yàn)檫@里stack里存的可能不連續(xù)。
                area = Math.max(area, heights[top]*(stk.isEmpty()? i: i-(stk.peek()+1)));
                i--;
            }
        }
        return area;
    }