题目链接：436 · 最大正方形
题目
题意
在地图里找到，连续的 全为 1 的 最大的 正方形 的面积
解题思路
因为前两天刚学了马拉车，我一看这【连续，相等】的字眼，就以为是二维马拉车，结果WA
在隔壁大佬的提示下发现这题很简单：判断一个点时
- 先看它上方有几个 1
- 左边有几个 1
- 左上角的方块边长是多少
- 三个数据组合起来就可以确定要不要把当前这个点加入变出更大的方块
- 最后可以考虑用滚动数组优化一下，因为每个点存的都是状态，因此只需要记录 这一行 和 上一行 的状态即可
所以我们要做的是
- 初始化第一行的状态，因为是最顶端，所以方块的边长就是
1 or 0 - 遍历
第 2 行到最后一行依次遍历每一行的内容- 如果是第 1 列的话直接把方块变成设置成
1 or 0 - 如果当前位置是
0的话直接将边长设置为0因为0无法加入方块 - 如果是
1的话，选取 左；左上；上 三个方向中边长最小的之后再+1即可ps：滚动数组就是
行标 i 对 2 取余 [i & 1] 或 [i % 2]就可以依次选择不同的行了
- 如果是第 1 列的话直接把方块变成设置成
- 在
初始化第一行；初始化第一列；为 1 加入方块三个位置把结果取一下最大值即可
代码
这里就直接帖炼码上的代码模板了，其实跟传统的 ACM 相比力扣、炼码这种刷题平台就是把 屏幕的输入输出 变成了类方法的 参数和 return
//
// _ _ ___ ____ ___ ____ _____
//| | | | / _ \ _ __ / ___/ _ \| _ \| ____|
//| |_| | | | | | '_ \ | | | | | | | | | _|
//| _ | | |_| | | | | | |__| |_| | |_| | |___
//|_| |_|___\___/|_| |_| \____\___/|____/|_____|
// |_____|
//
class Solution {
public:
int maxSquare(vector<vector<int>> &matrix) {
// write your code here
vector<int> v[2];
int maxium_square = 0;
for (int n : matrix[0]) {
v[0].push_back(n);
maxium_square = max(maxium_square, n);
v[1].push_back(0);
}
for (int i = 1; i < matrix.size(); i++)
for (int j = 0; j < matrix[0].size(); j++) {
if (!j) {
v[i & 1][j] = matrix[i][j];
// 这里跳过了下面的流程，所以别忘记取一下结果的最大值，因为上面取最大值只遍历了第一行，所以这里不取最大值会出错
maxium_square = max(maxium_square, v[i & 1][j]);
continue;
}
if (!matrix[i][j]) {v[i & 1][j] = 0; continue;}
v[i & 1][j] = min(v[i & 1][j - 1], min(v[!(i & 1)][j], v[!(i & 1)][j - 1])) + 1;
maxium_square = max(maxium_square, v[i & 1][j]);
}
return maxium_square*maxium_square;
}
};