題目

給定一個整數(shù)map酌住，其中的值只有0和1兩種叼旋，求其中全是1的所有矩形區(qū)域中最大的矩形區(qū)域?yàn)?的數(shù)量伴挚。
??例如：
?? 1 1 1 0
其中靶衍，最大矩形區(qū)域有3個1，所以返回3茎芋。
??例如：
?? 1 0 1 1
?? 1 1 1 1
?? 1 1 1 0
其中颅眶，最大的矩形區(qū)域有6個1，所以返回6田弥。

要求

如果矩陣為O(NxM),做到時間復(fù)雜度為O(NxM)

思路

??1.矩陣的行數(shù)為N涛酗，以每一行做切割，統(tǒng)計(jì)以當(dāng)前行作為底的情況下偷厦，每個位置往上的1的數(shù)量商叹。使用高度數(shù)組 height米表示。
??例如：
?? map = 1 0 1 1
????? 1 1 1 1
????? 1 1 1 0
??以第1行做切割后只泼，height＝{1,0,1,1}剖笙， height[j]表示在目前的底（第1行)的 j 位置往上(包括 j 位置)，有多少個續(xù)的1请唱。
??以第2行做切割后弥咪， height＝{2,1,2,2}， height[j]表示在目前的底(第2行)的 j 位置往上(包括 j 位置)籍滴，有多少個連續(xù)的1酪夷。注意到從第一行到第二行，height數(shù)組的更新是十分方便的孽惰，height[j]=map[i][j]==0 ? 0 : height[j]+1晚岭。
??以第3行做切割后， height＝{3,3,2,0}勋功， height表示在目前的底(第3行)的 j 位置往上(包括j位置)坦报，有多少個連續(xù)的1库说。
??2.對于每一次切割，都利用更新后的 height數(shù)組來求出以當(dāng)前行為底的情況下片择，最大的矩形是什么潜的。那么這么多次切割中，最大的那個矩形就是我們要的答案
??整個過程就是如下代碼中的 maxrecsize方法字管。步驟2的實(shí)現(xiàn)是如下代碼中的maxrecfrom Bottom方法啰挪。
??下面重點(diǎn)介紹一下步操2如何快速地實(shí)現(xiàn)，這也是這道題最重要的部分嘲叔，如果height數(shù)組的長度為M亡呵，那么求解步2的過程可以做到時問復(fù)雜度為O(M)
??對于 height數(shù)組，讀者可以理解為一個直方圖硫戈，比如{3,2,3,0}锰什，其實(shí)就是如下圖所示的直方圖。

示意圖

??也就是說丁逝，步驟2的實(shí)質(zhì)是在一個大的直方圖中求最大矩形的面積汁胆，如果我們能夠求出以每一根柱子擴(kuò)展出去的最大矩形，那么其中最大的矩形就是我們想找的霜幼。比如:
??● ? 第1根高度為3的柱子向左無法擴(kuò)展嫩码，它的右邊是2，比3小罪既，所以向右也無法擴(kuò)最谢谦，則以第1根柱子為高度的矩形面積就是3 * 1==3；
??● ? 第2根高度為2的柱子向左可以擴(kuò)1個距離萝衩，因?yàn)樗淖筮吺?回挽，比2大;右邊的柱子也是3，所以向右也可以擴(kuò)1個距離猩谊，則以第2根柱子為高度的矩形面積就是2 * 3==6;
??● ? 第3根高度為3的柱子向左沒法擴(kuò)展千劈，向右也沒法擴(kuò)展。以第3根框子為高度的矩形面積就是3 * 1==3牌捷；
??● ? 第4根高度為0的柱子向左沒法擴(kuò)晨墙牌，向右也沒法擴(kuò)展，則以第4根柱子為高度的短形面積就是0 * 1==0暗甥；
??所以喜滨，當(dāng)前直方圖中最大的矩形面積就是6，也就是上圖中虛線框住的部分撤防。
??考查每一根柱子最大能擴(kuò)多大虽风，這個行為的實(shí)質(zhì)就是找到柱子左邊離它最近且比它小的柱子位置在哪里，以及右邊離它最近且比它小的柱子位置在哪里，這個過程怎么計(jì)算最快呢?利用單調(diào)辜膝，如果對單調(diào)棧不是特別清楚的讀者可以去查看我寫的單調(diào)棧結(jié)構(gòu)
??為了方便表述无牵，我們以 height＝{3,4,5,4,3,6}為例說明如何根據(jù) height數(shù)組求其中的最大矩形。具體過程如下：
?? 1. 生成一個棧厂抖，記為stack從左到右遍歷height數(shù)組茎毁，每歷一個位置，都會把位置壓stack中忱辅。
?? 2. 遍歷到height的0位置七蜘，height[0] = 3,此時stack為空，直接將位置壓入棧中墙懂，此時stack從棧頂?shù)綏５诪閧0}崔梗。
?? 3. 通為到height的1位置，height[1]＝4垒在，此時stack的棧頂為位置0，值為 height[0]=3扔亥，又有height[1] > height[0]场躯，那么將位置1直接壓入stack。這一步體現(xiàn)了遍歷過程中的一個關(guān)鍵邏輯旅挤；只有當(dāng)前 i 位置的值height[i]大于當(dāng)前棧頂位置所代表的值( height[stack.peek()])踢关，則 i 位置才可以壓入 stack。
??所以可以知道粘茄，stack中從棧頂?shù)綏５椎奈恢盟淼闹凳且来芜f減并且無重復(fù)值签舞，此時stack從棧頂?shù)綏５诪閧1,0}。
?? 4. 遍歷到height的2位置柒瓣，height[2] = 5儒搭，與步驟3的情況完全一樣，所以直接將位置2壓入stack芙贫，此時stick從棧頂?shù)降诪閧2,1,0}搂鲫。
?? 5.遍歷到 height的3位置褒傅， height[3] = 4辉阶，此時stack的棧頂為位置2，值為 height[2]＝5磁滚，又有 heght[3] < height[2]拣挪，此時又出了一個遍過程中的關(guān)鍵邏輯擦酌，即如果當(dāng)前 i 位置的值 height[i]小于或等于當(dāng)前棧頂位置所代表的值(height[stack.peek()])，則把棧中存的位置不斷彈出菠劝，直到某一個棧頂所代表的值小于height[i]赊舶，再把 i 位置壓入，并在這期間做如下處理:
??1)假設(shè)當(dāng)前彈出的棧頂位置記為位置 j，彈出棧頂之后锯岖，新的棧頂記為k介袜。然后開始考慮位置 j 的柱子向右和向左最遠(yuǎn)能擴(kuò)到哪里。
??2)對位置 j 的柱子來說出吹，向右最遠(yuǎn)能擴(kuò)到哪里呢?
??如果 height[j] == height[i]遇伞，那么 j -1 位置就是向右能擴(kuò)到的最遠(yuǎn)位置。j 之所以被彈出捶牢，就是因?yàn)橛龅搅说谝粋€比 j 位置值小的位置鸠珠。
??如果 height[j]＝height[i]，那么j -1位置不一定是向右能擴(kuò)到的最遠(yuǎn)位置秋麸，只是起碼能擴(kuò)到的位置渐排。那怎么辦呢?
??可以肯定的是，在這種情況下灸蟆，i 位置的柱子向左必然也可以擴(kuò)到 j 位置驯耻。也就是說，j 位置的柱子擴(kuò)出來的最大矩形和 i 位置的柱子擴(kuò)出來的最大矩形是同一個炒考。
??所以可缚，此時 j 位置的柱子能擴(kuò)出來的最大矩形雖然無法被正確計(jì)算，但不要緊斋枢，因?yàn)?i 位置肯定要壓入到棧中帘靡，那么 j 位置和 i 位置共享的最大矩形就等 i位置彈出的時候再計(jì)算即可。
??3)對 j 位置的柱子來說瓤帚，向左最遠(yuǎn)能擴(kuò)到哪望呢?
??根據(jù)單調(diào)的性質(zhì)描姚，k 位置的值是 j 位置的值左邊離 j 位置最近的比 j 位置的值小的位置，所以 j 位置的柱子向左最遠(yuǎn)可以擴(kuò)到 k+1 位置戈次。
??4)綜上所述轩勘，j 位置的柱子能擴(kuò)出來的最大矩形為(i-k-1) * height[j]。
以例子來說明怯邪。
?? ① i == 3赃阀， height[3] ＝ 4，此時 stack的棧頂為位置2擎颖，值為height[2] = 5榛斯，故 heights[3]<= height[2]，所以位置2被彈出(j == 2)搂捧，當(dāng)前棧頂變?yōu)?(k == 1)驮俗。位置2的柱子擴(kuò)出來的最大矩形面積為(3-1-1) * 5 == 5。
?? ② i == 3, height[3] = 4允跑，此時 stack的項(xiàng)為位置1王凑，值為 height[1]＝4搪柑。故 height[3]<= height[2],所以位置1被彈出(j == 1)，當(dāng)前核頂變?yōu)?(k＝0)索烹。位置1的柱子擴(kuò)出來的最大矩形面積為(3-0-1) * 4==8工碾，這個值實(shí)際上是不對的(偏小)，但在位置3被彈出的時候是能夠重新正確計(jì)算得到的百姓。
?? ③ i ==3 渊额，height[3]＝4，此時 stack的棧頂為位置0垒拢，值為 heigh[0]＝3旬迹，這時 height[3]<= height[2]，所以位置0不彈出求类。
?? ④ 將位置3壓入 stack奔垦， stack從根頂?shù)胶说诪閧3,0}
??6. 遍歷到height的4位置， height[4]＝3尸疆、與步驟5的情況類似椿猎，以下是彈出過程:
??1) i==4， height[4]＝3寿弱，此時 stack的棧頂為位置3犯眠，值為 height[3]＝4，故 height[4]<= height[3]脖捻，所以位置0被彈出(j==0)，當(dāng)前棧頂變?yōu)?(k＝0)兆衅。位置3的柱子擴(kuò)出來的最大矩形面積為(4-0-1) * 4＝12地沮。這個最大面積也是位置1的柱子擴(kuò)出來的最大矩形面積，在位置1被彈出時羡亩，這個矩形其實(shí)沒有找到摩疑，但在位置3這里找到了。
??2) i==4畏铆， height[4]＝3雷袋，此時 stack的棧頂為位置0，值為 height[0]＝3辞居，故 height[4]<= heigh[0]楷怒，所以位置0被彈出(j==0)，當(dāng)前沒有了棧頂元素瓦灶，此時可以認(rèn)為k==-1鸠删。位置0的柱子擴(kuò)出來的最大矩形面積為(4-(-1)-1) * 3＝12，這個值實(shí)際上是不對的(偏小)贼陶，但在位置4被彈出時是能夠重新正確計(jì)算得到的刃泡。
??3)己經(jīng)為空巧娱，所以將位置4壓入 stack，此時從頂?shù)降诪椋?}烘贴。
??7. 遍歷到height的5位置禁添，height[5]＝6，情況和步驟3類似桨踪，直接壓入位置5老翘，此時從頂?shù)降诪閧5,4｝。
??8. 遍歷結(jié)束后馒闷，stack中仍有位置沒有經(jīng)歷擴(kuò)的過程酪捡，從棧頂?shù)綏５诪閧5,4}，此時因?yàn)?height數(shù)組再往右不能擴(kuò)出去纳账，所以認(rèn)為 i ＝ height.length==-6且越界之后的值極小逛薇，然后開始彈出留在棧中的位置:
??1) i==6，height[6]極小疏虫，此時 stack的頂為位置5永罚，值為 height[5]＝6，故 height[6]<=height[5]卧秘，所以位置5被彈出(j==5)呢袱，當(dāng)前棧頂變?yōu)?(k＝4)。位置5的柱子擴(kuò)出來的最大矩形面積為(6-4-1) * 6=6
??2) i==6翅敌，height[6]極小羞福，此時stack的棧頂為位置4，值為height[4]＝3蚯涮，故 height[6] <= height[4]治专，所以位置4被彈出(j==4)，椩舛ィ空了张峰，此時可以認(rèn)為k＝-1，位置4的柱子擴(kuò)出來的最大矩形面積為(6-(-1)-1) * 3==18棒旗。這個最大面積也是位置0的柱子擴(kuò)出來的最大矩形面積喘批，在位置0被彈出的時候，這個矩形其實(shí)沒有找到铣揉，但在位置4這里找到了饶深。
??3)棧已經(jīng)空了，過程結(jié)束逛拱。
??9. 整個過程結(jié)束粥喜，所有找到的最大矩形面積中18是最大的，所以返回18
??研究以上9個步驟時我們發(fā)現(xiàn)橘券，任何一個位置都僅僅進(jìn)出1次额湘，所以時向復(fù)余度為O(M)卿吐。既然每做一次切割處理的時間復(fù)雜度O(M)，一共做N次锋华，那么總的時間復(fù)雜度為O(NxM)嗡官。
??全部過程參看如下代碼中的 makrecsiie方法，9個步驟的詳翻過程參看代碼中的maxRecFromBottom方法毯焕。

代碼演示

package com.itz.zcy.stackAndQueue;

import java.util.Stack;

/**
 * 給定一個整數(shù)map衍腥，其中的值只有0和1兩種，求其中全是1的所有矩形區(qū)域中最大的矩形區(qū)域?yàn)?的數(shù)量纳猫。
 *  例如：
 *   1 1 1 0
 * 其中婆咸，最大矩形區(qū)域有3個1，所以返回3芜辕。
 *  例如：
 *  1 0 1 1
 *  1 1 1 1
 *  1 1 1 0
 * 其中尚骄，最大的矩形區(qū)域有6個1，所以返回6侵续。
 */
public class MaxRec {

    /**
     * 每一行切割后對每一行使用單調(diào)棧的結(jié)構(gòu)來他們最大能擴(kuò)大矩形面積
     * @param height
     * @return
     */
    public static int maxRecFromBottom(int [] height){
        if(height == null||height.length ==0){
            return 0;
        }
        int maxArea = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i=0;i<height.length;i++){
            while (!stack.isEmpty()&&height[i]<=height[stack.peek()]){
                int j = stack.pop();
                int k = stack.isEmpty()?-1:stack.peek();
                int curArea = (i-k-1)*height[j];
                maxArea = Math.max(maxArea,curArea);
            }
            stack.push(i);
        }
        while (!stack.isEmpty()){
            int j = stack.pop();
            int k = stack.isEmpty()?-1:stack.peek();
            int curArea = (height.length-k-1)*height[j];
            maxArea = Math.max(maxArea,curArea);
        }
        return maxArea;
    }

    /**
     * 對每一行進(jìn)行切割
     * @param map
     * @return
     */
    public int maxRecSize(int [][] map ){
        if (map == null||map.length==0||map[0].length==0){
            return 0;
        }
        int maxArea = 0;
        int [] height = new int[map.length];
        for (int i=0;i<map.length;i++){
            for (int j=0;j<map[0].length;j++){
                height[j] = map[i][j] == 0?0:height[j]+1;
            }
            maxArea = Math.max(maxRecFromBottom(height),maxArea);
        }
        return maxArea;
    }
}

總結(jié)

究以上9個步驟時我們發(fā)現(xiàn)倔丈，任何一個位置都僅僅進(jìn)出1次，所以時向復(fù)余度為O(M)状蜗。既然每做一次切割處理的時間復(fù)雜度O(M)(單調(diào)棧)需五，一共做N次，那么總的時間復(fù)雜度為O(NxM)轧坎。

文獻(xiàn)：左程云著 《程序員代碼面試指南IT名企算法與數(shù)據(jù)結(jié)構(gòu)題目最優(yōu)解》（第二版）
版權(quán)聲明：此文版權(quán)歸作者所有宏邮！