ReMind

Recent Writing

See 247 more →

矩形牛棚_(单调栈，优化)

5 min read

原题链接：1413. 矩形牛棚 - AcWing题库

题意：给定矩阵，有一些坏点，要求最大的内部无坏点的矩阵

思路

写得时候没想到

遍历

明确要做遍历，发现对数据范围 或者说 可以过

如果暴力搜，那就得 想办法优化，首先是前缀和优化高度

如果分开上下两个自由度遍历来求每列中连通的矩阵有多长的话，那就得（上下不固定，从左到右遍历）

可以用前缀和，逐步往下数，数到坏点就重新数，可以优化掉一维

考虑到，经典题型——直方图求最大面积

可以固定下边界（或者说遍历下边界），此时从当前下边界到上边界的距离可以用上述的前缀和确定，也就是确定了两边，接下来找左右

要怎么找才是最大矩阵呢？首先是矩阵，下边界确定了，那就得上边界高度一致才可以，或者两边高度比当前列高才可以拓展为矩阵，那就涉及到找到数组中左边比自己小的数 与 右边比自己小的数

用单调栈，从起点遍历，设定边界值（最好设定到不需要考虑边界问题），先将边界值入栈，然后数组开始遍历，例如找左边比自己小的数，当前栈顶不是该数索引就出栈，直到找到了，将当前索引入栈

这样是单调查找的，被弹掉的数绝对不会是下一次要找的第一个满足条件的数，例如找左边比自己小的数，弹掉了一些数，说明那些数比自己大，如果下一个数找左边第一个小数，则一定会先找到自己，弹掉的数不影响

实现

#include <iostream>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
const int N = 3010;
 
int n, m, p;
int g[N][N];
int h[N][N], l[N], r[N];
 
//枚举下边界后剩下对直方图的面积求极值
int get_max(int h[])
{
    //预处理边界避免麻烦的讨论，这样就无论如何找得到小值
    h[0] = h[m + 1] = -1;
    
    int stack[N] = {};
    int top = 0;
    stack[ ++ top] = 0;
    
    //找左边
    for(int i = 1; i <= m; i ++)
    {
        //最左边已经被赋值-1
        while(h[stack[top]] >= h[i]) top --;
        
        l[i] = stack[top];
        //弹掉的都比当前大，当前值入栈，如果被弹掉，之前比当前大的数在下一个数的查找中也没有用处
        stack[++ top] = i;
    }
    
    //找右边，先入右边边界
    top = 0;
    //用++ top 是为了区别开 0 和 m+1
    stack[++ top] = m + 1;
    
    for(int i = m; i > 0; i --)
    {
        while(h[stack[top]] >= h[i]) top --;
        
        r[i] = stack[top];
        stack[++ top] = i;
    }
    
    
    int res = 0;
    for(int i = 1; i <= m; i ++)
    {
        res = max(res, h[i] * (r[i] - l[i] - 1));
    }
    
    return res;
}
 
 
int main()
{
    cin >> n >> m >> p;
    
    //memset(g, 0, sizeof g);
    
    for(int i = 0; i < p; i ++)
    {
        int a, b;
        cin >> a >> b;
        
        g[a][b] = 1;
    }
    
    
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
        {
            //预处理每行高度，是坏掉的就重新数
            if(!g[i][j])
                h[i][j] = h[i - 1][j] + 1;
        }
        
    int ans = 0;
    //遍历下边界
    for(int i = 1; i <= n; i ++)
    {
        int max_now = get_max(h[i]);
        ans = max(ans, max_now);
    }
    
    cout << ans << endl;
    
    return 0;
}

Graph View