[Leetcode] Largest Rectangle (in Histogram) 最大矩形

鄒強發布于2019-08-14 12:24 / 1194人閱讀

摘要：以此類推，如果一直到棧為空時，說明剛出來的豎條之前的所有豎條都比它自己高，不然不可能棧為空，那我們以左邊全部的寬度作為長方形的寬度。

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.

暴力法 復雜度

時間 O(N^2) 空間 O(1)

思路

最直觀的方法是對每個豎條，都向前向后計算下最大的面積，這樣雖然時間復雜度很高，但是不用額外空間。

棧法 復雜度

時間 O(N) 空間 O(N)

思路

遍歷數組（直方圖），如果后一個豎條高于或等于前一個豎條，則將其下標push進棧，如果后一個豎條（假設它的下標為i）較矮，說明可以開始計算前一個豎條(i-1)及之前那塊上升區域最大的長方形面積了，這時將棧頂的豎條的下標pop出來，計算該豎條的面積。然后再看pop過后棧頂豎條(i-2)和后一個豎條(i)的大小關系，如果棧頂豎條(i-2)較矮，說明又構成了一個連續上升區域，則將后一個豎條(i)push進棧，否則繼續計算棧頂豎條(i-2)的面積，這里要注意，因為(i-2)豎條比(i-1)豎條要靠左，所以i-2豎條能構成的最大長方形的寬度可以達到2，寬度的計算方法是用后一個豎條的下標i，減去再pop一個元素后棧頂豎條的下標(i-3)，再加上1。以此類推，如果一直pop到棧為空時，說明剛pop出來的豎條之前的所有豎條都比它自己高，不然不可能棧為空，那我們以左邊全部的寬度作為長方形的寬度。這里計算寬度時，要減去上一個豎條的位置，而不是減去當前豎條的位置，因為有可能上一個豎條和當前豎條之間已經有些豎條被pop掉了，但他們肯定是高于當前豎條的，所以可以計算到寬度中。

代碼

public class Solution {
    public int largestRectangleArea(int[] height) {
        if(height.length == 0) return 0;
        Stack stk = new Stack();
        int i = 1, max = height[0];
        stk.push(0);
        while(i < height.length || (i == height.length && !stk.isEmpty())){
            // i==height.length 說明目前棧頂已經是最后一個豎條，那就要開始pop了
            if(i != height.length && ( stk.isEmpty() || height[i] >= height[stk.peek()] )){
                stk.push(i);
                i++;
            } else {
                // pop后棧為空的話說明之前所有豎條都比剛pop出來的矮
                int top = height[stk.pop()];
                int currMax = !stk.isEmpty() ? top * (i - stk.peek() - 1) : top * i;
                max = Math.max(currMax, max);
            }
        }
        return max;
    }
}

Maximal Rectangle

Given a 2D binary matrix filled with 0"s and 1"s, find the largest rectangle containing all ones and return its area.

動態規劃 + 棧 復雜度

時間 O(NM) 空間 O(M)

思路

這題的解法基于上題。要求最大的矩形，實際上可以將矩陣的每一行，轉化為上一題的直方圖，而直方圖的每個豎條的數字，就是該行對應坐標正上方，向上方向有多少個連續的1。要轉化為直方圖，方法是每一行的數值都累加上一行計算出來的數值，而第一行的數值就是本身。如果原始矩陣中遇到0，則累加中斷，重新置0。

0 0 1 1 0 -> 0 0 1 1 0
0 0 1 1 0 -> 0 0 2 2 0
1 1 0 0 0 -> 1 1 0 0 0
1 1 1 0 0 -> 2 2 1 0 0

代碼

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        int max = 0;
        if(matrix.length == 0) return 0;
        int[][] dp = new int[matrix.length][matrix[0].length];
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                // 如果是第一行就是自身，如果遇到0則停止累加
                dp[i][j] =  i == 0 ? matrix[i][j] - "0" : matrix[i][j] == "1" ? dp[i-1][j] + matrix[i][j] - "0" : 0;
            }
        }
        for(int i = 0; i < dp.length; i++){
            //找每行的最大矩形
            int tmp = findRowMax(i, dp);
            max = Math.max(max, tmp);
        }
        return max;
    }
    
    private int findRowMax(int row, int[][] matrix){
        if(matrix[row].length== 0) return 0;
        Stack stk = new Stack();
        int i = 1, max = matrix[row][0];
        stk.push(0);
        while(i < matrix[row].length || (i == matrix[row].length && !stk.isEmpty())){
            if(i != matrix[row].length && ( stk.isEmpty() || matrix[row][i] >= matrix[row][stk.peek()] )){
                stk.push(i);
                i++;
            } else {
                int top = matrix[row][stk.pop()];
                int currMax = !stk.isEmpty() ? top * (i - stk.peek() - 1) : top * i;
                max = Math.max(currMax, max);
            }
        }
        return max;
    }
}

云服務器 GPU云服務器 HISTOGRAM Largest Rectangle LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64450.html

leetcode84. Largest Rectangle in Histogram

摘要：題目要求即找到圖中可以組合而成的面積最大的矩形。從而我們可以知道該矩形在水平方向上的最大擴展程度。也就是說，棧中數據記錄了最遠左側下標，而當前的矩形則是最遠右側下標。當我們不采用數據結構時，尋找和計算的過程需要的時間復雜度。題目要求 Given n non-negative integers representing the histograms bar height where t...

Harpsichord1207 2019-08-15 10:55 評論0 收藏0
Largest Rectangle in Histogram

摘要：而最大的矩形一定滿足兩個邊界的高度小于該矩形的高度這個條件如果不滿足的話，邊界也可以被添加進來計算而不破壞矩形的形狀，此時不為最大，因此找出所有這樣的矩形就一定可以在其中找出面積最大的矩形。 Problem Given n non-negative integers representing the histograms bar height where the width of e...

vvpvvp 2019-07-24 17:33 評論0 收藏0
[LintCode] Largest Rectangle in Histogram

摘要：只要出現當前右邊界高度小于等于棧頂元素高度的情況，就取出棧頂元素當前遍歷過最高的并對這個元素進行取最大矩形的運算。 Problem Given n non-negative integers representing the histograms bar height where the width of each bar is 1, find the area of largest ...

alighters 2019-08-14 15:27 評論0 收藏0
[LeetCode] 84. Largest Rectangle in Histogram

Problem Given n non-negative integers representing the histograms bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. showImg(https://segmentfault.com/img...

BaronZhang 2019-08-16 14:25 評論0 收藏0
84. Largest Rectangle in Histogram

摘要：要求一個矩形的面積，要知道高和寬。如果每次確定高度為然后調用一個找到左右邊界，即不小于的最左和最右。這是一個明顯的算法，每次掃描都會重走整個。一個遞增序列這種，我們知道可以夠成的矩形是會不斷增大的。遞增序列預處理，遞減的時候計算。 showImg(https://segmentfault.com/img/bVoQel); For example, Given heights = [2,...

melody_lql 2019-08-14 18:01 評論0 收藏0