动态规划_leetcode.1504.统计全1子矩形

发表于 | 分类于 ， | 热度: ℃
字数统计: 2.4k | 阅读时长 ≈ 10

🌸题目

🍁给你一个只包含 0 和 1 的 rows * columns 矩阵 mat ，请你返回有多少个 子矩形 的元素全部都是 1 。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
输入：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：

1
2
3
4
5
6
7
8
9
10
11
12
13
输入：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 。

示例 3：

1
2
3
4
5
6
输入：mat = [[1,1,1,1,1,1]]
输出：21
示例 4：

输入：mat = [[1,0,1],[0,1,0],[1,0,1]]
输出：5

提示：

  • 1 <= rows <= 150
  • 1 <= columns <= 150
  • 0 <= mat[i][j] <= 1

🌸解法一、暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int numSubmat(int[][] mat) {
    int ans=0;
    int n=mat.length;
    if(n==0)
        return 0;
    int m= mat[0].length;
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++){
            // i,j为左上角顶点,固定左上角,逐行遍历右下角
            int p=Integer.MAX_VALUE;// 矩形右边界
            for(int a=i;a<n;a++){
                for(int b=j;b<m&&b<p;b++){
                    // a,b为右下角顶点
                    if(mat[a][b]==1){
                        ans++;
                    } else {
                        p=b;// 更新边界
                        break;
                    }
                }
            }
        }
    }
    return ans;
}

🌸解法二、动态规划（枚举）

🍁首先很直观的想法,我们可以枚举矩阵中的每个位置(i, j),统计以其作为右下角时,有多少个元索全部都是1的子矩形，那么我们就能不重不漏地统计出满足条件的子矩形个数。那么枚举以后，我们怎么统计满足条件的子矩形个数呢?

既然是枚举以(i, j)作为右下角的子矩形个数,那么我们可以直接暴力地枚举左上角(k,y),看其组成的矩形是否满足条件,时间复杂度为O(nm)。但这样无疑会使得时间复杂度变得很高,我们需要另寻他路。

我们预处理row数组,中row[i] [j]代表矩阵中(i,j)向左延伸连续1的个数,容易得出递推式:
$$
row[i][j]=\begin{cases}0,&\text{mat[i][j] = 0}\row[i][j - 1] + 1,&\text{mat[i][j] = 1}\end{cases}
$$
有了row数组以后，如果要统计以(i, j)为右下角满足条件的子矩形,我们就可以枚举子矩形的高，即第k行，看当前高度有多少满足条件的子矩形。于我们知道第k行到第i行「每一行第j列向左延伸连续1的个数」row[k] [j],….row[i] [j],],因此我们可以知道第k行满足条件的子矩形个数就是这些值的最小值，它代表了「第 k行到第i行子形的宽的最大值」， 公式化来说，即:min{row[l] [j]}(l = k...i)

因此我们倒序枚举k,用col变量来记录到当前行row的最小值，即能在0(n)的
时间内统计出以(i, j)为右下角满足条件的子矩形个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public int numSubmat1(int[][] mat) {
	int n = mat.length;
	int m = mat[0].length;
	int[][] row = new int[n][m];
	
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(j == 0) {
				row[i][j] = mat[i][j];
			}else if(mat[i][j] != 0) {
				row[i][j] = row[i][j - 1] + 1;
			}else {
				row[i][j] = 0;
			}
		}
	}
	int ans = 0;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			int col = row[i][j];
			for(int k = i; k >=0 && col != 0; --k) {
				col = Math.min(col, row[k][j]);
				ans += col;
			}
		}
	}
	return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        n, m = len(mat), len(mat[0])
        
        row = [[0] * m for _ in range(n)]
        for i in range(n):
            for j in range(m):
                if j == 0:
                    row[i][j] = mat[i][j]
                else:
                    row[i][j] = 0 if mat[i][j] == 0 else row[i][j - 1] + 1
        
        ans = 0
        for i in range(n):
            for j in range(m):
                col = row[i][j]
                for k in range(i, -1, -1):
                    col = min(col, row[k][j])
                    if col == 0:
                        break
                    ans += col
        
        return ans

🌸解法三、单调栈

🍁单调栈是一种特殊的栈，它始终保证栈里的元素具有单调性,要么是单调递增， 要么是单调递减，在此题中我们需要维护一个存储row值的单调栈，满足从栈底到栈顶的元素单调递增。为什么会想到这么做?这因为我们会发现，最容易统计的情况是row[0..i] [j] 的值随行号单调递增，此时答案就是它们的和,但是如果遇到非递增的时候，即当前row[i] [j]小于当前row[i- 1] [j],此时无疑i- 1行row[i- 1] [j]- row[i] [j] 的部分我们是不再需要的，它对后面i+1,i+ 2,… ,n一1统计答案的时候都不会再用到，这个时候我们就可以抛弃掉这部分的值，然后再去看row[i] [j]和row[i - 2] [j] 的值,以此类推，直到row[j[j]的值大于当前单调栈栈顶的元素时结束,然后再推row[i] [j].

这就是维护-一个单调栈的过程，但是还没完，我们不能简单地将不满足条件的值从栈里弹出，以上面第i- 1行举例，它有row[i] [j] 大小的部分是需要统计入答案的,
这个时候我们需要怎么做呢?

我们对单调栈存储的元素进行修改，改成存储-个二 元组(row[i] [j], height),示当
前矩形的宽和高，一开始我们放入的单调栈的都是高为 1宽为row[i] [j]的矩形，但碰到上面情况的时候，为了保留弹出元素中可用部分」的答案,我们需要将当前要推入栈中的元素的高加上弹出元素的高，于这个情况只会发生在推入元素小于栈顶元素的时候发生，因此矩形的宽一是当前推入元素的row值，同时我们再维护一个到当前行的答案和sum值即可。

通过单调栈的使用，我们就不再需要每次枚举的时候再重复倒序枚举k了,进一步优化了时间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public int numSubmat2(int[][] mat) {
        int n = mat.length;
        int m = mat[0].length;
        int[][] row = new int[n][m];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (j == 0) {
                    row[i][j] = mat[i][j];
                } else if (mat[i][j] != 0) {
                    row[i][j] = row[i][j - 1] + 1;
                } else {
                    row[i][j] = 0;
                }
            }
        }
        int ans = 0;
        for (int j = 0; j < m; ++j) { 
            int i = 0;
            Deque<int[]> Q = new LinkedList<int[]>();
            int sum = 0; 
            while (i <= n - 1) { 
                int height = 1; 
                while (!Q.isEmpty() && Q.peekFirst()[0] > row[i][j]) {
                  	// 弹出的时候要减去多于的答案
                    sum -= Q.peekFirst()[1] * (Q.peekFirst()[0] - row[i][j]); 
                    height += Q.peekFirst()[1]; 
                    Q.pollFirst(); 
                } 
                sum += row[i][j]; 
                ans += sum; 
                Q.offerFirst(new int[]{row[i][j], height}); 
                i++; 
            } 
        } 
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        n, m = len(mat), len(mat[0])
        
        row = [[0] * m for _ in range(n)]
        for i in range(n):
            for j in range(m):
                if j == 0:
                    row[i][j] = mat[i][j]
                else:
                    row[i][j] = 0 if mat[i][j] == 0 else row[i][j - 1] + 1
        
        ans = 0
        for j in range(m):
            Q = list()
            total = 0
            for i in range(n):
                height = 1
                while Q and Q[-1][0] > row[i][j]:
                    # 弹出的时候要减去多于的答案
                    total -= Q[-1][1] * (Q[-1][0] - row[i][j])
                    height += Q[-1][1]
                    Q.pop()
                total += row[i][j]
                ans += total
                Q.append((row[i][j], height))

        return ans

🌸解法四、与运算

🍁对于只有一行数组而言，比如[1,1,1,0,1,1,1,1,0,1]
前3个1,能组成3个1x1，2个1x2， 1个 1x3, - 共3+2+1=6种情况
中间4个1,能组成4个1x1, 3个1x2，2个1x3，1个1x4, -共4+3+2+1=10种情况
所以能找到-种规律，连续出现的n个1,可以组成1 +2+3+…+n种情况，使
公式，就是n*(n+1)/2种情况
上面是只有一行的情况。
对于2行而言，比如

1
2
0,1,1,0,0,1,1,1,1
0,0,1,0,1,0,0,1,1

只有第3列能组成2x1，后两列能组成1个2x2,2个2x1,

我们可以发现，只有在同一列，全部都是1时才能起到作用，对于其他的地方,
1的存在是没有意义的,
这个结果和只有1行的[0, 0, 1 ,0,0, 0,0,1, 1]的结果是一样的。
2行变成1行，通过观察可以发现，可以使用与运算&实现。
对于3行，4行，..n行同理，都可以转化成1行来计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public int numSubmat3(int[][] mat) {
    int result = 0;
    for (int i = 0; i < mat.length; i++) {
        int[] nums = new int[mat[i].length];
        System.arraycopy(mat[i], 0, nums, 0, mat[i].length);

        result += getRes(nums);

        for (int j = i + 1; j < mat.length; j++) {
            for (int k = 0; k < mat[j].length; ++k) {
                nums[k] = nums[k] & mat[j][k];
            }
            result += getRes(nums);
        }
    }
    return result;
}

//计算1行
public int getRes(int[] nums) {
    int result = 0;     //结果
    int continuous = 0;  //连续出现的1的个数
    for (int num : nums) {
        if (num == 0) {
            result += continuous * (continuous + 1) / 2;
            continuous = 0;
        } else {
            continuous++;
        }
    }
    result += continuous * (continuous + 1) / 2;
    return result;
}

最后，不经历风雨,怎能在计算机的大山之顶看见彩虹呢！ 无论怎样，相信明天一定会更好！！！！！

-------------本文结束感谢您的阅读-------------
云澈 wechat
扫一扫，用手机访问哦
坚持原创技术分享，您的支持将鼓励我继续创作！
0%