P用于存放原矩阵子矩阵的和，P[i][j]表示矩阵mat[1][1]至[i][j]的和，若要求[a][b]到[c][d]的和，则用P[c][d] - P[a][d] - P[c][b] + P[a][b]
class Solution { public: int maxSideLength(vector<vector<int>>& mat, int threshold) { int row = mat.size(); int col = mat[0].size(); vector<vector<int>> P(row + 1, vector<int> (col + 1, 0)); for (int i = 1; i <= row; ++i) { for (int j = 1; j <= col; ++j) { P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + mat[i-1][j-1]; } } int left = 1, right = min(row, col), ans = 0; while (left <= right) { int mid = (left + right) >> 1; bool find = false; for (int i = 1; i <= row - mid + 1; ++i) { for (int j = 1; j <= col - mid + 1; ++j) { if (P[i+mid-1][j+mid-1] - P[i+mid-1][j-1] - P[i-1][j+mid-1] + P[i-1][j-1] <= threshold) { find = true; } } } if (find) { ans = mid; left = mid + 1; } else { right = mid - 1; } } return ans; }