> 这个题目数据范围是n,m≤100n,m \leq100n,m≤100,就算先进行二维前缀和优化,然后枚举左上角和右下角坐标,时间复杂度为O(n4)O(n^4)O(n4),极有可能超时,但是实际上可以通过,就需要进行优化
步骤 1:前缀和预处理(二维转一维辅助)
首先计算矩阵的二维前缀和,目的是快速计算任意子矩形的元素和。
前缀和数组 a[i][j]a[i][j]a[i][j] 定义:表示以 (1,1)(1,1)(1,1) 为左上角、(i,j)(i,j)(i,j)为右下角的子矩形的元素和(注意:代码中直接在原矩阵上修改存储前缀和,空间优化)。
前缀和公式:a[i][j]=原a[i][j]+a[i−1][j]+a[i][j−1]−a[i−1][j−1]a[i][j] = 原a[i][j] + a[i-1][j] + a[i][j-1] - a[i-1][j-1]a[i][j]=原a[i][j]+a[i−1][j]+a[i][j−1]−a[i−1][j−1](容斥原理,避免重复计算)。
前缀和在这里不进行赘述
步骤 2:枚举行范围(压缩维度 O(N2)O(N^2)O(N2))
枚举所有可能的 “上下行边界” 组合 (i,j)(i为上行,j为下行,1≤i≤j≤n)(i,j)(i 为上行,j 为下行,1≤i≤j≤n)(i,j)(i为上行,j为下行,1≤i≤j≤n):
对于每个固定的行范围 [i,j][i,j][i,j],问题转化为:在这 j−i+1j-i+1j−i+1 行中,找到一个列范围 (l,r](l,r](l,r],使得该列范围内的元素和 ≥k≥k≥k,且矩形面积 (j−i+1)∗(r−l)(j-i+1)*(r-l)(j−i+1)∗(r−l) 最小。
> 从第 iii 行到第 jjj 行,第 l+1l+1l+1 列到第第 rrr 列 的面积就是 (j−i+1)∗(r−l)(j-i+1)*(r-l)(j−i+1)∗(r−l)
步骤 3:滑动窗口找最小列范围(一维优化 O(M)O(M)O(M))
对于固定的行范围 [i,j][i,j][i,j],用双指针(滑动窗口) 遍历列:
右指针 rrr 从 111 到 mmm 逐步扩展(扩大窗口右边界)。
左指针 lll 初始为 000 (不包含第 lll 列的数据 ),当窗口内的和 ≥k≥k≥k 时,尝试右移 lll 缩小窗口,直到和 <k<k<k,期间不断更新最小面积。
窗口和计算:利用前缀和快速得到 [i,j][i,j][i,j] 行、[l+1,r][l+1,r][l+1,r] 列的子矩形和:sum=a[j][r]−a[j][l]−a[i−1][r]+a[i−1][l]sum = a[j][r] - a[j][l] - a[i-1][r] + a[i-1][l]sum=a[j][r]−a[j][l]−a[i−1][r]+a[i−1][l]。
最终代码(时间复杂度O(n2m)O(n^2m)O(n2m))