??不說(shuō)廢話了，直接貼題

題意

給你一個(gè)二維矩陣，權(quán)值為False和True，找到一個(gè)最大的矩形，使得里面的
值全部為T(mén)rue，輸出它的面積

樣例

給你一個(gè)矩陣如下

[
  [1, 1, 0, 0, 1],
  [0, 1, 0, 0, 1],
  [0, 0, 1, 1, 1],
  [0, 0, 1, 1, 1],
  [0, 0, 0, 0, 1]
]
輸出6

1.建立模型

??這個(gè)題如果直接來(lái)解決的話，可能有很大的難度，所以，我們必須先建立模型。
??首先我們來(lái)看一個(gè)題，是LeetCode上：

題意

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].

樣例

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

(1).暴力解法

??這個(gè)題暴力解法非常的簡(jiǎn)單，就是遍歷數(shù)組，向前和向后計(jì)算當(dāng)前柱狀圖能夠構(gòu)成的最大矩形。至于解法這里不詳述，我們的目的引出另一個(gè)方法。

(2).棧法

??解題思路：首先我們將第一個(gè)柱狀圖在數(shù)組里面的下標(biāo)(之后稱為下標(biāo))壓棧，之后的柱狀圖需要我們來(lái)判斷是否需要壓棧。如果新的柱狀圖高度大于棧頂柱狀圖的高度，那么就當(dāng)前這個(gè)柱狀圖的下標(biāo)壓棧；如果小于的話，那么我們可以計(jì)算當(dāng)前棧頂及其之前的柱狀圖面積，于是，我們將棧頂?shù)南聵?biāo)pop出來(lái)，計(jì)算它的面積。
??pop之后，我們?cè)俅闻袛喈?dāng)前的棧頂?shù)母叨仁欠翊笥谛轮鶢顖D的高度，如果大于，則壓棧；反之，則計(jì)算面積，這里計(jì)算面積的時(shí)候需要注意的是：計(jì)算pop出來(lái)的柱狀圖的面積(從pop出來(lái)的柱狀圖到新的柱狀圖，不包含新的柱狀圖，因?yàn)樾碌闹鶢顖D的高度小于當(dāng)前pop出來(lái)的高度)高度等于它本身的高度，而寬度則是當(dāng)前的新的柱狀圖的下標(biāo)-pop出來(lái)的之后的棧頂?shù)南聵?biāo) - 1。
??為什么是這樣呢？因?yàn)閜op出來(lái)的之后的棧頂柱狀圖與pop出來(lái)的柱狀圖之間可能還有其他柱狀圖，只是在之前的操作被pop出去了，所以，這里需要這樣計(jì)算寬度。
??如果理解了思路，那么代碼就非常理解了

public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        Stack<Integer> stack = new Stack<>();
        //壓入第一個(gè)柱狀圖的下標(biāo)
        stack.push(0);
        int i = 1;
        int max = heights[0];
        //當(dāng)i < heights.length 或者棧不為空時(shí)，這里之所以需要判斷棧不為空，是因?yàn)?        //可能有些高度很小的柱狀圖，一直停留在棧中，沒(méi)有機(jī)會(huì)pop出來(lái)計(jì)算面積，所以最后需要一一的pop出來(lái)
        //計(jì)算面積
        while (i < heights.length || (i == heights.length && !stack.isEmpty())) {
            //當(dāng)當(dāng)前的高度大于大于棧頂?shù)母叨然蛘邨榭諘r(shí)，將當(dāng)前的下標(biāo)壓棧
            if (i < heights.length && (stack.isEmpty() || heights[stack.peek()] <= heights[i])) {
                stack.push(i);
                i++;
            } else { //計(jì)算面積
                int top = heights[stack.pop()]; //得到棧頂?shù)母叨?                //計(jì)算面積，當(dāng)當(dāng)前的棧為空時(shí)，直接是top * i（i里面已經(jīng)包含了中間被pop出去的柱狀圖）；不為空時(shí)，
                //則使用相對(duì)位置計(jì)算
                int currMax = !stack.isEmpty() ? (i - stack.peek() - 1) * top : top * i;
                //更新最大值
                max = Math.max(max, currMax);
            }
        }
        return max;
    }

2.利用模型解決問(wèn)題

??現(xiàn)在回到我們要解決的問(wèn)題上去，我們利用類似于上面的方法來(lái)解決，將數(shù)組轉(zhuǎn)換：

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

??需要注意的是，轉(zhuǎn)換的規(guī)則是：每行的遍歷，如果當(dāng)前位置(假設(shè)nums[i][j])為true，那么dp[i]j = dp[i - 1][j - 1]；反之，如果為false，則置為0。當(dāng)i = 0時(shí)，另當(dāng)別論。
??數(shù)組轉(zhuǎn)換成功之后，我們只需要計(jì)算每一行的最大矩形面積，其中dp數(shù)組中0,1,2之類的表示的這個(gè)矩形的高度，當(dāng)每一行的最大矩形都計(jì)算出來(lái)之后，取得最大值自然是最終的答案

public int maximalRectangle(boolean[][] matrix) {
        if (matrix == null || matrix[0].length == 0) {
            return 0;
        }
        //轉(zhuǎn)換之后的數(shù)組
        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++) {
                if (i == 0) {
                    //i = 0的情況
                    dp[i][j] = matrix[i][j] ? 1 : 0;
                } else {
                    //不等于0
                    dp[i][j] = matrix[i][j] ? dp[i - 1][j] + 1 : 0;
                }
            }
        }
        int max = 0;
        //遍歷每一行
        for (int i = 0; i < matrix.length; i++) {
            //取得每一行的最大值
            int temp = findRowMax(dp[i]);
            //更新最大值
            max = Math.max(max, temp);
        }
        return max;
    }

    private int findRowMax(int[] heights) {
        if (heights.length == 0) {
            return 0;
        }
        Stack<Integer> stack = new Stack<>();
        stack.push(heights[0]);
        int i = 1;
        int max = heights[0];
        while (i < heights.length || (i == heights.length && !stack.isEmpty())) {
            if (i < heights.length && (stack.isEmpty() || heights[i] >= heights[stack.peek()])) {
                stack.push(i);
                i++;
            } else {
                int height = heights[stack.pop()];
                int currMax = !stack.isEmpty() ? (i - stack.peek() - 1) * height : height * i;
                max = Math.max(currMax, max);
            }
        }
        return max;
    }