Solution

cookiebus 2023-05-20 6:06:30 29 返回题目

这道题目是在二维平面内求解长度为 的正方形的最值,最容易想到的方法是求解每一行所有长度为k的区间最值,

然后在列的方向上再求解一遍最值得到的就是以当前列为右端点的长度为的区间最值,而在行方向上或者列方向上求解最值实际上是一维平面内滑动窗口求最值的问题,可以使用单调队列优化,我们可以求解出每一行与每一列的最值之后保存到对应的两个数组上即可(row_min保存行最小值,row_max保存行最大值),

每一次求解以当前列的位置作为右端点的长度为的正方形的最值,枚举每一列对应的所有正方形的最值即可得到所有长度为k的正方形的最值,在枚举的时候更新答案即可。

本题还可以使用 ST表解决

算法类型:ST表 or 单调队列

{{ vote && vote.total.up }}