html网站搭建,WordPress建站如何解析,长春微网站,天津 做网站题目:
给你一个 m x n 的二进制矩阵 mat #xff0c;请你返回有多少个 子矩形 的元素全部都是 1 。
示例 1#xff1a; 输入#xff1a;mat [[1,0,1],[1,1,0],[1,1,0]]
输出#xff1a;13
解释#xff1a;
有 6 个 1x1 的矩形。
有 2 个 1x2 的矩形。
有 3 个 2x1 的矩…
题目:
给你一个 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个矩形。
但是第三行和第二行组合
即第二行和第三行的第一列组成一个矩形
第二行和第三行的第二列组成一个矩形
第二行和第三行的第一列与第二列也可以组成一个矩形
不仅如此第一行、第二行、第三行的第一列也可以组成一个矩阵;
因此第三行新增的矩阵个数为31111 7个。
总矩形数量就是 2 4 7 13个。 单调栈单调栈结构可以快速的找到任意一个数左、右侧比自己大(或小)的数字的下标。
我们按照单调栈的思想把以上的数组再推导一遍。此时数组是
1 0 1
1 1 0
1 1 0
第一行 2个矩形
数组压缩以后第二行变成 2 1 0.
高度为2只有1个矩形
高度为1可以得到下标0和1. 2-1* (2 * 21/2 ) 3个
因此第二行累计是 1 3 4个矩形。
第三行数组压缩以后变成 3 2 0
高度为3的只有1个矩形
高度为22*2*(21)/2 6个
因此这个数组累计矩形为 2 4 16 13 个矩形 如果还不理解我再举个例子
假设数组为 1 1 1 我们根据公式可得 3 * (31)/2 6
假设再增加一行
1 1 1
1 1 1
第一行是6个
第二行是 3 * (31)/2 6但是第一行和第二行联合起来还可以拼 3 * (31)/2 6 也就是说第二行实际新增了 2*6 12
假设再增加一行
1 1 1
1 1 1
1 1 1
那第一行是 1* 3 * (31)/2 6
第二行是 2* 3 * (31)/2 12
第三行就是 3 * 3 * (31)/2 18个
1对应1行2对应2行3对应3行。 现在用压缩数组的角度再来看
第一行 1 1 1. 根据 1* 3 * (31)/2 6
第二行变成了 2 2 2. 根据 2* 3 * (31)/2 12
第三行变成了 3 3 3 根据 3* 3 * (31)/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 * (31)/2 6
第二行是 2* 3 * (31)/2 12
第三行就是 3 * 3 * (31)/2 18个
第四行就要分情况了
首先以高度为4的情况可得 3 * (31)/2 6
其次以高度为3的情况可得 3 * (31)/2 6
然后以高度为2的情况, 可得 3 * (31)/2 6
最后以1为高度的情况注意此时以高度为1的情况长度为4, 4 *41/2 10;
总的概括第四行就是前三行的组合
第四行与前三行组合不就是 4-1*3 * (31)/2 3* 6 18个矩形
第四行单独新增 (1-0)* (4 *41/2 10;
因此最终矩形数量为 6 12 18 66610 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*(11)/2) 1个* 再以高度为1的计算 1-0 * 2*21/2 3个* 合计 13 4个*** 如果在增加一行* 1 0 1 2 个矩形* 1 1 0 4 个矩形* 1 1 1 10 个矩形* 最后一行数组压缩成 3 2 1* 先算高度为3的 (3 - 2* (1*(11)/2) 1个* 再算高度为2的 (2 - 1) * (2*(21)/2) 3个* 最后算高度为1的 (1-0) * (3*(31)/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 * (n1) 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));}
} 测试结果
