算法39：统计全 1 子矩形（力扣1504）----单调栈

题目:

给你一个 m x n 的二进制矩阵 mat ，请你返回有多少个 子矩形 的元素全部都是 1 。

示例 1：

输入：mat = [[1,0,1],[1,1,0],[1,1,0]]
输出：13
解释：
有 6 个 1x1 的矩形。
有 2 个 1x2 的矩形。
有 3 个 2x1 的矩形。
有 1 个 2x2 的矩形。
有 1 个 3x1 的矩形。
矩形数目总共 = 6 + 2 + 3 + 1 + 1 = 13 。

示例 2：

输入：mat = [[0,1,1,0],[0,1,1,1],[1,1,1,0]]
输出：24
解释：
有 8 个 1x1 的子矩形。
有 5 个 1x2 的子矩形。
有 2 个 1x3 的子矩形。
有 4 个 2x1 的子矩形。
有 2 个 2x2 的子矩形。
有 2 个 3x1 的子矩形。
有 1 个 3x2 的子矩形。
矩形数目总共 = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24 。

这一题比较有意思，我花费了一周左右的时间才绕出来。下面来说一下我的解题思路。

1. 假设数组为 1 0 1, 我们知道它只有2个矩形

2 .那么如果数组变成了：

1 0 1

1 1 0.

我们知道第一行只有2个，

第二行可以是下标为0的{1}, 下标为1的{1}, 下标0和1的组合{1,1} 因此累计是3个；但是，我们还发现第一行和第二行的第一列也可以组成一个矩形。因此，第二行累计多出了4个矩形

3. 假设数组再增加一行：

此时，第三行单独新增了3个矩形。

但是第三行和第二行组合：

即第二行和第三行的第一列组成一个矩形；

第二行和第三行的第二列组成一个矩形；

第二行和第三行的第一列与第二列也可以组成一个矩形；

不仅如此，第一行、第二行、第三行的第一列也可以组成一个矩阵;

因此，第三行新增的矩阵个数为（3+1+1+1+1）= 7个。

总矩形数量就是 2 + 4 + 7 = 13个。

单调栈：单调栈结构可以快速的找到任意一个数左、右侧比自己大(或小)的数字的下标。

我们按照单调栈的思想，把以上的数组再推导一遍。此时，数组是：

1 0 1

1 1 0

第一行 2个矩形

数组压缩以后，第二行变成 2 1 0.

高度为2只有1个矩形；

高度为1，可以得到下标0和1. （2-1）* (2 * （2+1）/2 )= 3个

因此第二行累计是 1 + 3 = 4个矩形。

第三行数组压缩以后变成 3 2 0

高度为3的只有1个矩形

高度为2，2*（2*(2+1)/2）= 6个

因此，这个数组累计矩形为 2 + 4 + （1+6）= 13 个矩形

如果还不理解，我再举个例子

假设数组为 1 1 1，我们根据公式可得 3 * (3+1)/2 = 6；

假设再增加一行：

1 1 1

第一行是6个；

第二行是 3 * (3+1)/2 = 6；但是，第一行和第二行联合起来，还可以拼 3 * (3+1)/2 = 6；也就是说第二行实际新增了 2*6= 12；

假设再增加一行：

1 1 1

那第一行是 1* 3 * (3+1)/2 = 6；

第二行是 2* 3 * (3+1)/2 = 12；

第三行就是 3 * 3 * (3+1)/2 = 18个；

1对应1行，2对应2行，3对应3行。

现在用压缩数组的角度再来看：

第一行 1 1 1. 根据 1* 3 * (3+1)/2 = 6

第二行变成了 2 2 2. 根据 2* 3 * (3+1)/2 = 12

第三行变成了 3 3 3 根据 3* 3 * (3+1)/2 = 18

有没有发现，公式前面的 1 2 3和压缩数组的数组元素高度出奇的一致？

现在把数组变化一下，左侧是原始数组，右侧是进行数组压缩后的结果

1 1 1 0 === 1 1 1 0

1 1 1 0 ==== 2 2 2 0

1 1 1 0 ==== 3 3 3 0

1 1 1 1 ==== 4 4 4 1

那第一行是 1* 3 * (3+1)/2 = 6；

第二行是 2* 3 * (3+1)/2 = 12；

第三行就是 3 * 3 * (3+1)/2 = 18个；

第四行就要分情况了：

首先：以高度为4的情况，可得 3 * (3+1)/2 = 6

其次，以高度为3的情况，可得 3 * (3+1)/2 = 6

然后，以高度为2的情况, 可得 3 * (3+1)/2 = 6

最后，以1为高度的情况，注意，此时以高度为1的情况长度为4, 4 *（4+1）/2 = 10;

总的概括，第四行就是前三行的组合：

第四行与前三行组合不就是（4-1）*（3 * (3+1)/2 ）= 3* 6 = 18个矩形

第四行单独新增 (1-0)* (4 *（4+1）/2） = 10;

因此，最终矩形数量为： 6 + 12 + 18 + （6+6+6+10）= 64个矩形；

package code04.单调栈_01;

/**
 * 力扣1504， 统计全1矩阵
 * https://leetcode.com/problems/count-submatrices-with-all-ones
 */
public class Code05_SumOfRectangleForAllOne {

    public int numSubmat(int[][] mat)
    {
        if (mat == null || mat.length == 0) {
            return 0;
        }
        int sum = 0;
        int[] help = new int[mat[0].length];
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[i].length; j++) {
                //数组压缩
                help[j] = mat[i][j] == 0 ? 0 : help[j] + 1;
            }
            sum += countRectangle(help);
        }

        return sum;
    }

    public int countRectangle(int[] help)
    {
        int size = help.length;
        //自定义栈结构
        int[] stack = new int[size];
        int stackSize = 0;

        int ans = 0;
        for (int i = 0; i < size; i++)
        {
            //如果栈中元素比当前数组i对应的数据大，弹出栈中数据
            while (stackSize != 0 && help[stack[stackSize-1]] > help[i]) {
                //弹出栈顶元素
                int cur = stack[--stackSize];
                //左侧比弹出的cur小的位置
                int left = stackSize == 0 ? -1 : stack[stackSize -1];
                //确保单调栈的连通性，获取左、有两侧比当前cur小的值中较大的数
                int max = Math.max(left == -1 ? 0 : help[left],  help[i]);
                //统计cur作为最小值的范围
                int quantity = i - 1 - left;


                /**
                 * help[cur] - max 代表高度中高出的部分. 比如
                 * 1 0 1 中有2个矩形
                 *
                 * 再增加一行
                 * 1 0 1   = 2个
                 * 1 1 0   = 4个
                 * 此时数组压缩成了2 1 0
                 * 此时的 help[cur] - max就代表 2 - 1. 即高度为2的部分单独算
                 * 而count(quantity) 就代表高度为2的连续元素有多少个
                 *
                 * 根据压缩后的数组 2, 1, 0，推导第二行矩形个数
                 * 先以高度为2的计算 (2-1) * (1*(1+1)/2) = 1个
                 * 再以高度为1的计算 （1-0） * （2*（2+1）/2） = 3个
                 * 合计 1+3 =4个
                 *
                 *
                 * 如果在增加一行
                 *  1 0 1      = 2 个矩形
                 *  1 1 0      = 4 个矩形
                 *  1 1 1      = 10 个矩形
                 *  最后一行数组压缩成 3 2 1
                 *  先算高度为3的 (3 - 2）* (1*(1+1)/2) = 1个
                 *  再算高度为2的 (2 - 1) * (2*(2+1)/2) = 3个
                 *  最后算高度为1的 (1-0) * (3*(3+1)/2) = 6个
                 *  合计 1+ 3 + 6 = 10个
                 *
                 * 那么，如果数组为
                 *  1 0 1
                 *  1 1 0
                 *  1 1 1
                 *
                 *  那么，总的矩形就是 2 + 4 + 10 = 16个
                 *
                 */
                ans += (help[cur] - max) * count(quantity);
            }
            stack[stackSize++] = i;
        }

        while (stackSize != 0) {
            //弹出栈顶元素
            int cur = stack[--stackSize];
            //左侧比弹出的cur小的位置
            int left = stackSize == 0 ? -1 : stack[stackSize -1];
            //确保单调栈的连通性
            int max = Math.max(left == -1 ? 0 : help[left], 0);
            //统计cur作为最小值的范围
            int quantity = size - 1 - left;

            ans +=  (help[cur] - max)  * count(quantity);
        }
        return ans;
    }

    public int count (int n) {
        return n * (n+1) >> 1;
    }

    public static void main(String[] args) {
        Code05_SumOfRectangleForAllOne ss = new Code05_SumOfRectangleForAllOne();
        int[][] mat = {
            {1,0,1},
            {1,1,0},
            {1,1,1}
        };
        System.out.println(ss.numSubmat(mat));

    }
}

测试结果