题目大意:
给出一个矩阵, 和M ,找到一个最大的子矩阵,使得里面的最大值-最小值的差值小于 M
思路:
- 关键信息是最大和最小, 就保留这个信息即可
- 然后考虑如何枚举每一个矩阵?
- 枚举矩阵的上下边界, 然后在考虑矩阵的左右边界,
- 左右边界处理的时候, 这一列的最大最小值,可以通过枚举上下边界的时候线性DP出来
- 然后这样子就转为1维, 明显符合单调性 利用双指针On的处理
- 处理的时候在更具 只保留 关键最大最小的信息, 利用2个单调队列去保存, 下标递增,值根据最大最小递增,(新的树进来,就去删除不符合的数彳于了)
- L 的变化: 当有不符合的情况的时候, 就把 l -> min(最大坐标,最小的坐标)+1 就ok了