题目链接：nowcoder多校3-Planting Trees

题意：

给定一个n×n的矩阵，然后需要找到一个最大的子矩阵满足子矩阵中的任意两个数之差小于m，最后输出子矩阵大小。

题解：

首先枚举子矩阵的上下边界，同时维护当前上下界的每列最大值和最小值。

然后开始枚举右边界，对于左边界可以使用二分或数据结构来求，但是可能会超时。

枚举右边界的同时，维护两个单调队列（手写双端队列，用STL遭TLE了QAQ）:

1. 最小值单调队列为下标递增，大小递增。
2. 最大值单调队列为下标递增，大小递减。

每次计算当前队首元素是否满足条件并更新答案。

参考代码：

#include <bits/stdc++.h>
#define IL inline
using namespace std;
typedef long long ll;
typedef double db;
const int MAXN = 5e2 + 2;
const int inf = 0x3f3f3f3f;
int T;
int n, m;
int a[MAXN][MAXN];
int maxv[MAXN], minv[MAXN];
int minn[MAXN], maxn[MAXN];
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                scanf("%d", &a[i][j]);
        int ans = 0;
        for (int i = 1; i <= n; i++) //枚举上边界
        {
            memset(maxv, -1, sizeof(maxv));
            memset(minv, inf, sizeof(maxv));
            for (int j = i; j <= n; j++) //枚举下边界
            {
                for (int k = 1; k <= n; k++) //维护当前上下边界中每一列的最大值和最小值
                {
                    maxv[k] = max(maxv[k], a[j][k]);
                    minv[k] = min(minv[k], a[j][k]);
                }
                int l = 1;
                int h1, h2, t1, t2;
                h1 = h2 = 1, t1 = t2 = 0;
                for (int r = 1; r <= n; r++) //枚举右边界
                {
                    while (h1 <= t1 && minv[r] <= minv[minn[t1]]) //最小值单调队列 维护下标递增 大小递增
                        t1--;
                    minn[++t1] = r;
                    while (h2 <= t2 && maxv[r] >= maxv[maxn[t2]]) //最大值单调队列 维护下标递增 大小递减
                        t2--;
                    maxn[++t2] = r;
                    while (l <= r && maxv[maxn[h2]] - minv[minn[h1]] > m)
                    {
                        l++;
                        if (minn[h1] < l)
                            h1++;
                        if (maxn[h2] < l)
                            h2++;
                    }
                    ans = max(ans, (j - i + 1) * (r - l + 1));
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}