全部由1组成的子矩形的数量
题目描述：
给定一个二维数组matrix，其中的值不是0就是1，返回全部由1组成的子矩阵的数量。
way：
假设我们遍历矩形的每一行，以当前遍历到的行作为地基，去看这一行的直方图（直方图介绍 ->直方图的最大长方形面积-CSDN博客）中全部由1组成的子矩阵的个数，将每一行得到的子矩阵数加起来，得到答案，将二维问题转变为了一维问题，所以就是像下面这样。
第一行：1 1 1 1 0 1
第二行：2 2 2 2 0 2
第三行：3 3 3 3 1 3
第四行: 0 4 4 4 2 4 （做地基时如果有0直接为0，地基都没有，上面的没法垒起来的）
第五行：1 5 0 5 3 5
为了明显点，假设这5行中的有一行是 3, 2, 4, 2, 5，那么计算这一行的直方图的子矩阵的数量就是，以当前行的每个元素作为所在子矩阵中的最小高度，得到一块区域，假设以第4个2作为最低高度，那么可以得到如下的一块区域，在这个区域中，对于高度为2的子矩阵的数量，有1-1列，1-2列，1-3列，1-4列，1-5列，2-2列，2-3，2-4，2-5，3-3，3-4，3-5，4-4，4-5，5-5 这(1+5)*5/2=15个，对于高度为1的数量，也有15个，所以如果区域长度为L，高度为h，那么子矩阵的数量就是 L * (L+1)/2 * h 个，对于上面说的，有 5 *（5+1）/2 *2 = 30个，这个高度h为当前选的最低高度 - max(left, right) （left，right 分别为它的左右两边离它最近且比它 小于or等于 的数，就像第一个2，左边比它小的数没有，右边比它 等于 的数是第2个2，然后h=2-2=0, 没有计算以第一个2为最小高度时的子矩阵数，到了第2个2的时候，左边比它小的数没有，右边比它小的数也没有，h=2-0=2, 到了第2个2的时候才计算了下面的阴影部分的子矩阵的数量，这样就不会算重复，只会在最后一个2的时候去计算以2为最低高度的时候那块高度为2连通的大区域的子矩阵数，必须是 小于等于，必须是 h = 高度差，这样就不会在 最低高度 =3 的时候去计算高度为2的子矩阵数，那样高度为2的区域其实还没有完全连起来形成一块大区域，会算重）。注意要一行一行的做地基 (地基必被算）得到一个个直方图数组去算去加和，其实你按我上面的说法1-1，1-2，1-3....，不同高度这样一行一行的去算就知道对不对了。
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
int subMatrixCount(vector<int> height)
{
int N = height.size();
stack<int>st;
int num = 0;
for (int i = 0; i < N; i++)
{
while (!st.empty() && height[i] <= height[st.top()])
{
int topIndex = st.top();
st.pop();
int leftIndex = st.empty() ? -1 : st.top();
int rightIndex = i;
//(rightIndex-1)-(leftIndex+1) + 1
int L = rightIndex - 1 - leftIndex;
int h = height[topIndex] - max(height[rightIndex], leftIndex >= 0 ? height[leftIndex] : 0);
num += L * (L + 1) / 2 * h;
}
st.push(i);
}
while (!st.empty())
{
int topIndex = st.top();
st.pop();
int leftIndex = st.empty() ? -1 : st.top();
int rightIndex = N;
//(rightIndex-1)-(leftIndex+1) + 1
int L = rightIndex - 1 - leftIndex;
int h = height[topIndex] - max(0, leftIndex >= 0 ? height[leftIndex] : 0);
num += L * (L + 1) / 2 * h;
}
return num;
}
int allSubMatrixCountBy1(vector<vector<char>> mp)
{
if (mp.size() == 0) return 0;
int M = mp.size();
int N = mp[0].size();
vector<int>row(N);
int sum = 0;
for (int i = 0; i < M; i++)
{
for (int j = 0; j < N; j++)
{
if (mp[i][j] == '1')
{
row[j] += 1;
}
else
{
row[j] = 0;
}
}
sum += subMatrixCount(row);
}
return sum;
}
int main()
{
vector<vector<char>> mp = {
{'1', '1'},
{'1', '1'}
};
int sum = allSubMatrixCountBy1(mp);
cout << sum << endl; //9
return 0;
}
原文地址：https://blog.csdn.net/qinghehe198508/article/details/140582118
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！