TheRiver | blog

You have reached the world's edge, none but devils play past here

0%

1504 Count Submatrices With All Ones

Posted on Edited on
Symbols count in article: 2.3k Reading time ≈ 2 mins.

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

1 solution

动态规划算法，比较好理解，对于1d的数组，总的矩形个数是:

对于2d的数组，可以先算1d的个数，然后每次加上上一行的数组，合起来算最小宽度的新的数组的个数，这样可以涵盖所有的情况，如图:

代码如下：

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
37
// 1 solution 动态规划
class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        int m = mat.size();
        int n = mat[0].size();
        int res = 0;

        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (mat[i][j])
                    mat[i][j] += j == 0 ? 0 :mat[i][j - 1];
            }
        }

        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (mat[i][j] > 0)
                {
                    res += mat[i][j];
                    auto small = mat[i][j];
                    for (int k = i - 1; k >= 0 && mat[k][j] > 0; --k)
                    {
                        small = min(mat[k][j], small);
                        res += small;
                    }   
                }
            }
        }

        return res;
    }
};

时间复杂度 O(mmn)

空间复杂度 O(1)

2 solution

单调栈算法，上面动态规划其实只是横向的动态规划，纵向每次都还要往上遍历包含重复的情况。而且往上有个规律就是上面宽度只能小于等于当前的宽度，这样才能构成新的矩形。这里存在单调性的情况，所以可以考虑用单调栈，但这个实现起来非常麻烦，我也是看着官方题解想了半天

可以先回顾下算柱状图中最大矩形的时候怎么用单调栈的:

1
2
3
4
5
6
7
8
push i = 0
pop i = 0,  max = 2 * 1 
push i = 1
push i = 2
push i = 3
pop i = 3,  max = 3 * 1
pop i = 2,  max = 2 * 2
pop i = 1,  max = 1 * 4

这里稍加转换可以用在本题，入栈的时候加上栈内的值的和就可以了，也就是

1
2
push i = 2, h[2] + h[1]
push i = 3, h[3] + h[2] + h[1]

直接这样写还是不行的，因为已经出栈i = 0, 也有一个1会被后面的使用，这是个理解的难点。因此题解里面栈内存的是pair(i, height), 也就是加了个高度。默认入栈高度为1，对于栈内元素全部出栈后接着入栈的第一个元素，高度要加上前面的pop元素的高度。说多了容易被语言困扰，看代码:

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// 2 solution 单调栈
class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        int m = mat.size();
        int n = mat[0].size();
        int res = 0;
        vector<int> heights(m + 1, 0);

        auto addMutiRow = [&m, &res](vector<int>& heights) {
            int count = 0;
            // (row, high) 
            stack<pair<int, int>> st;
            st.push(make_pair(0, 0));
            int i = 1; 
            int sum = 0;
            int high = 1;
            while (i < m + 1)
            {
                auto top = st.top();
                if (heights[i] >= heights[top.first])
                {
                    sum += heights[i];                    
                    count += sum;
                    st.push(make_pair(i++, high));
                    high = 1;
                } 
                else
                {
                    st.pop();  
                    high += top.second;
                    sum -= ((heights[top.first] - heights[i]) * top.second);        
                }
            }

            return count;
        };

        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (mat[i][j])
                    mat[i][j] += j == 0 ? 0 :mat[i][j - 1];   
            }
        }

        for (int j = 0; j < n; ++j)
        {
            for (int i = 0; i < m; ++i)
                heights[i + 1] = mat[i][j];

            int num = addMutiRow(heights);
            res += num;
        }

        return res;
    }

};

总结

无意间发现了这道题，动态规划挺好理解的，单调栈看了思路后尝试自己写，结果写了半天没写出来，淦啊。然后钻牛角尖浪费了不少时间，就这样吧

----------- ending -----------