2019牛客暑期多校训练营（第八场）A-All-one Matrices（单调栈+思维）

痛定思痛。 2021-10-29 12:48 153阅读 0赞

[>传送门<][Link 1]

**题意：**给你一个01矩阵，求出所有**不可扩大**的全为1的矩阵的个数

**思路：**比赛的时候想到了用单调栈，但是也只是想到了，并不知道怎么用，其实和之前求[二维01矩阵中全为1的矩阵最大面积][01_1]非常相像。

像到什么地步呢！！你想一个不能扩大的矩阵，也即是说不能向左右扩展，也不能向上扩展，那我们就用单调栈维护每一行中每个点能向上扩展的最大高度**h。**

目前到这里都和二位01矩阵求最大面积的解法一模一样！！接下来我们只需要判断这个矩阵能不能向下扩展就行了，对吧。这里我们就用数组记录一下，如果能向下扩展就记为1，不能就记为0，最后判断，这个矩阵向左右扩展的最大区间宽度是否大与向下扩展的宽度，如果大与的话就不能向下扩展。

最后还有一个问题，不知道有没有发现，假如我在同一行两次查找到的矩阵是同一矩阵，那怎么办？

这个时候就涉及到去重的问题了，仔细观察一下，会发现同一高度的**h**值在出栈计算得到的矩形是一样的（因为高度相同的肯定能互相扩展），所以**高度相同的只用计算一次**就好了。我们比较一下弹出的元素和栈顶元素的**h**值，如果相同就代表高度相同就不能取。

**Code**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    const int maxn = 3005;
    
    int n, m, t, ans;
    int a[maxn][maxn];
    int st[maxn], h[maxn], dn[maxn];
    char c[maxn];
    int main()
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            scanf("%s", c+1);
            for (int j = 1; j <= m; j++) a[i][j] = c[j]-'0'; 
        }
        for (int i = 1; i <= n; i++) {
            int t = 0; //t表示栈顶 
            for (int j = 1; j <= m + 1; j++) {
                h[j] = a[i][j] ? h[j] + 1 : 0; //向上能扩展的最大高度 
                dn[j] = dn[j - 1] + a[i + 1][j]; //是某能向下扩展的前缀和 
                while (h[j]<h[st[t]]) {
                    int width = j-1-st[t-1], num = dn[j-1]-dn[st[t-1]]; //width表示能向左右扩展的最大宽度，num表示其中共有几个能够向下扩展 
                    ans += (num<width&&h[st[t-1]]<h[st[t]]); //判断是否满足条件并去重 
                    t--;
                }
                st[++t] = j;
            }
        }
        printf("%d\n", ans);
        return 0;
    }

转载于:https://www.cnblogs.com/wizarderror/p/11335771.html

[Link 1]: https://ac.nowcoder.com/acm/contest/888/A
[01_1]: https://www.cnblogs.com/wizarderror/p/11232097.html
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211029/088f78c0c5c64eae9683bff193fcacf2.png