成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

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

鄒強(qiáng) / 1201人閱讀

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

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.
暴力法 復(fù)雜度

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

思路

最直觀的方法是對(duì)每個(gè)豎條，都向前向后計(jì)算下最大的面積，這樣雖然時(shí)間復(fù)雜度很高，但是不用額外空間。

棧法 復(fù)雜度

時(shí)間 O(N) 空間 O(N)

思路

遍歷數(shù)組（直方圖），如果后一個(gè)豎條高于或等于前一個(gè)豎條，則將其下標(biāo)push進(jìn)棧，如果后一個(gè)豎條（假設(shè)它的下標(biāo)為i）較矮，說(shuō)明可以開始計(jì)算前一個(gè)豎條(i-1)及之前那塊上升區(qū)域最大的長(zhǎng)方形面積了，這時(shí)將棧頂?shù)呢Q條的下標(biāo)pop出來(lái)，計(jì)算該豎條的面積。然后再看pop過后棧頂豎條(i-2)和后一個(gè)豎條(i)的大小關(guān)系，如果棧頂豎條(i-2)較矮，說(shuō)明又構(gòu)成了一個(gè)連續(xù)上升區(qū)域，則將后一個(gè)豎條(i)push進(jìn)棧，否則繼續(xù)計(jì)算棧頂豎條(i-2)的面積，這里要注意，因?yàn)?i-2)豎條比(i-1)豎條要靠左，所以i-2豎條能構(gòu)成的最大長(zhǎng)方形的寬度可以達(dá)到2，寬度的計(jì)算方法是用后一個(gè)豎條的下標(biāo)i，減去再pop一個(gè)元素后棧頂豎條的下標(biāo)(i-3)，再加上1。以此類推，如果一直pop到棧為空時(shí)，說(shuō)明剛pop出來(lái)的豎條之前的所有豎條都比它自己高，不然不可能棧為空，那我們以左邊全部的寬度作為長(zhǎng)方形的寬度。這里計(jì)算寬度時(shí)，要減去上一個(gè)豎條的位置，而不是減去當(dāng)前豎條的位置，因?yàn)橛锌赡苌弦粋€(gè)豎條和當(dāng)前豎條之間已經(jīng)有些豎條被pop掉了，但他們肯定是高于當(dāng)前豎條的，所以可以計(jì)算到寬度中。

代碼 
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 說(shuō)明目前棧頂已經(jīng)是最后一個(gè)豎條，那就要開始pop了
            if(i != height.length && ( stk.isEmpty() || height[i] >= height[stk.peek()] )){
                stk.push(i);
                i++;
            } else {
                // pop后棧為空的話說(shuō)明之前所有豎條都比剛pop出來(lái)的矮
                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.
動(dòng)態(tài)規(guī)劃 + 棧 復(fù)雜度

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

思路

這題的解法基于上題。要求最大的矩形，實(shí)際上可以將矩陣的每一行，轉(zhuǎn)化為上一題的直方圖，而直方圖的每個(gè)豎條的數(shù)字，就是該行對(duì)應(yīng)坐標(biāo)正上方，向上方向有多少個(gè)連續(xù)的1。要轉(zhuǎn)化為直方圖，方法是每一行的數(shù)值都累加上一行計(jì)算出來(lái)的數(shù)值，而第一行的數(shù)值就是本身。如果原始矩陣中遇到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;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64450.html

相關(guān)文章

  • leetcode84. Largest Rectangle in Histogram

    摘要：題目要求即找到圖中可以組合而成的面積最大的矩形。從而我們可以知道該矩形在水平方向上的最大擴(kuò)展程度。也就是說(shuō)，棧中數(shù)據(jù)記錄了最遠(yuǎn)左側(cè)下標(biāo)，而當(dāng)前的矩形則是最遠(yuǎn)右側(cè)下標(biāo)。當(dāng)我們不采用數(shù)據(jù)結(jié)構(gòu)時(shí)，尋找和計(jì)算的過程需要的時(shí)間復(fù)雜度。 題目要求 Given n non-negative integers representing the histograms bar height where t...

    Harpsichord1207 評(píng)論0 收藏0

  • Largest Rectangle in Histogram

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

    vvpvvp 評(píng)論0 收藏0

  • [LintCode] Largest Rectangle in Histogram

    摘要：只要出現(xiàn)當(dāng)前右邊界高度小于等于棧頂元素高度的情況，就取出棧頂元素當(dāng)前遍歷過最高的并對(duì)這個(gè)元素進(jìn)行取最大矩形的運(yùn)算。 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 評(píng)論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 評(píng)論0 收藏0

  • 84. Largest Rectangle in Histogram

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

    melody_lql 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<