Largest Common Submatrix(2019银川K题)

链接:https://nanti.jisuanke.com/t/42391
题意:求两个矩阵的最大重叠面积
题解:单调栈(悬线法...(有些没看懂))
对于第二个矩阵的每一个位置求 表示第 位置可以和第一个矩阵相同可以到达的最高高度.
下来转换成对于每行的 求直方图的最大面积
如下:

int LargestRectangleArea(vector<int>& height){
    height.push_back(0);//为了统计，数组最后添加0，确保原数组的最后一位得到计算
    stack<int> s;
    int LargestArea = 0;
    int temp,i=0;
    while(i<(int)height.size()){
        if(s.empty()||(height[i]>height[s.top()])){
            s.push(i);
            i++;
        }
        else{
            temp = s.top();
            s.pop();
            LargestArea = max(LargestArea,height[temp]*(s.empty()?i:i-s.top()-1));
        }
    }
    return LargestArea;
}
单调栈解决

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 1e3 + 7;
int a[maxn][maxn],b[maxn][maxn];
int h[maxn][maxn];
int ans;
int n,m;

struct Node
{
    int x,y;
}mp1[maxn * maxn + 100],mp2[maxn * maxn + 100];

struct STK
{
    int l;
    int h,i;
}stk[maxn];

void solve(int j)//递增单调栈
{
    int top = 0;
    stk[top].h = 0;stk[top].i = 0;
    mp2[0].x = INF;mp2[0].y = INF;
    h[n + 1][j] = 0;
    int flag = 0;
    for(int i = 0;i <= n + 1;i++)stk[i].l = 0;
    for(int i = 1;i <= n + 1;i++)
    {
        if(mp1[b[i][j]].x == mp1[b[i - 1][j]].x + 1 && mp1[b[i][j]].y == mp1[b[i - 1][j]].y)
            flag = 1;
        else flag = 0;
        int l = 0,len = 0;
        while(top && (stk[top].h > h[i][j] || !flag))
        {
            int s = (stk[top].l + l + 1) * stk[top].h;
            l += stk[top].l + 1;
            ans = max(ans,s);
            top--;
        }
        stk[++top].h = h[i][j];stk[top].i = i;
        if(flag)stk[top].l = l;
        else if(!flag)stk[top].l = 0;
    }
}



int main()
{
    scanf("%d%d",&n,&m);

    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            scanf("%d",&a[i][j]);
            mp1[a[i][j]].x = i;
            mp1[a[i][j]].y = j;
        }
    }

    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            scanf("%d",&b[i][j]);
            mp2[b[i][j]].x = i;mp2[b[i][j]].y = j;
        }
    }

    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            if(mp1[b[i][j]].x == mp1[b[i][j - 1]].x && mp1[b[i][j]].y == mp1[b[i][j - 1]].y + 1)
            {
                h[i][j] = h[i][j - 1] + 1;
            }
            else h[i][j] = 1;
        }
    }

    for(int i = 1;i <= m;i++)
    {
        solve(i);
    }

    printf("%d\n",ans);
    return 0;
}