数据结构——线性表【矩阵】

一、矩阵遍历与简单操作

这类题目侧重考察矩阵的基本遍历逻辑（行遍历、列遍历、对角线遍历等），以及简单的元素修改。
Vector<String> 数组：

对于字符串有内置的find函数：
查找单个字符：string.find(char c)。例如 words[i].find(x)，就是在 words[i] 这个字符串中查找字符 x。
查找子串：string.find(const string& str)。例如 “abcdef”.find(“cd”)，会查找子串 “cd” 在 “abcdef” 中的位置。

1.1查找

1.1.1有序矩阵查找

给你一个满足下述两条属性的 m x n 整数矩阵：每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

整个矩阵可以看作一个按行拼接的有序一维数组。对于一维数组索引 mid，

• 对应的矩阵行索引为 row = mid / n（n 为每行元素数）。
• 对应的矩阵列索引为 col = mid % n。
  初始化左右指针 left = 0 和 right = m × n - 1。计算中间索引 mid，找到对应的矩阵元素。

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int m=matrix.size();
    int n=matrix[0].size();
    int left=0;
    int right=n*m-1;
    while(left<=right){
        int mid=left + (right -left)/2;
        int row=mid/n;
        int col=mid%n;
        if(matrix[row][col] == target) return 1;
        else if(target < matrix[row][col]) right=mid-1;
        else left=mid+1;
    }
    return false;
}

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int m = matrix.size();    
    int n = matrix[0].size(); 
    // 从右上角开始搜索
    int row = 0;
    int col = n - 1;
    while (row < m && col >= 0) {
        if (matrix[row][col] == target) return true;
        else if (matrix[row][col] > target) col--;
        else  row++;
    }
    return false;
}

1.1.2有序矩阵查找第K小的元素

给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。

// 计算矩阵中小于等于target的元素数量
int countLessOrEqual(vector<vector<int>>& matrix, int target) {
    int n = matrix.size();
    int count = 0;
    int row = 0;          // 从第一行开始
    int col = n - 1;      // 从最后一列开始
    
    while (row < n && col >= 0) {
        if (matrix[row][col] <= target) {
            // 当前行从第0列到col列的所有元素都小于等于target
            count += col + 1;
            row++;  // 移动到下一行
        } else {
            col--;  // 移动到前一列
        }
    }
    
    return count;
}
int kthSmallest(vector<vector<int>>& matrix, int k) {
    int n = matrix.size();
    // 矩阵中的最小值（左上角）和最大值（右下角）
    int left = matrix[0][0];
    int right = matrix[n - 1][n - 1];
    
    // 二分查找
    while (left < right) {
        int mid = left + (right - left) / 2;
        // 计算矩阵中小于等于mid的元素数量
        int count = countLessOrEqual(matrix, mid);
        
        // 根据count调整查找范围
        if (count < k) {
            // 第k小的元素在mid右侧
            left = mid + 1;
        } else {
            // 第k小的元素在mid左侧或就是mid
            right = mid;
        }
    }
    
    return left;
}

1.2行与列的问题

1.2.1二维数组求行列的最大值

int m=grid.size();          //行数
int n=grid[0].size();       //列数

vector<int> max1(m);        //每一行的最大值
vector<int> max2(n);         //每一列的最大值

for(int i=0;i<m;i++){//行
	for(int j=0;j<n;j++){//列
		max1[i]=max(grid[i][j],max1[i]);
		max2[j]=max(grid[i][j],max2[j]);
	}
}

1.2.2按某行 or 某列排序

for(int i=0;i<m;i++){
    sort(nums[i].begin(), nums[i].end());
}
for(int i=0; i<m; i++){
    sort(nums[i].rbegin(), nums[i].rend());  // 反向迭代器实现降序
}

按照某一列升序排序的代码如下所示：
如下图：根据K=2的那一列对整行进行排序：

#include <vector>
#include <algorithm>  // 用于 sort 函数

// 普通函数作为比较规则
bool compare(const vector<int>& a, const vector<int>& b, int k) {
    return a[k] > b[k];
}
vector<vector<int>> sortTheStudents(vector<vector<int>>& score, int k) {
    sort(score.begin(),score.end(),[k](const vector<int>& a, const vector<int>& b)
    	{return a[k]>b[k];}
    );
    return score;
}

[k](const vector<int>& a, const vector<int>& b){return a[k]>b[k];}是 lambda 表达式。

• [k]：k 是函数的参数，不在 lambda 内部定义，所以需要通过 [k] 捕获它才能使用。
• (const vector<int>& a, const vector<int>& b)：参数列表，需要比较的两个元素。
• return a[k] > b[k]：函数体，当 a 的第 k 个元素大于 b 的第 k 个元素时，a 应该排在 b 前面。

sort(matrix.begin(), matrix.end(), [col, ascending](const vector<int>& a, const vector<int>& b) {
    if (ascending) {
        return a[col] < b[col];  // 升序：按列值从小到大
    } else {
        return a[col] > b[col];  // 降序：按列值从大到小
    }
});

1.2.3矩阵置0

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。

void setZeroes(vector<vector<int>>& matrix) {
    int m=matrix.size();
    int n=matrix[0].size();
    vector<int> row(m,0);//记录哪些行有0
    vector<int> col(n,0);//记录哪些列有0
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(matrix[i][j]==0){
                row[i]=1;
                col[j]=1;
            }
        }
    }
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(row[i] || col[j]) matrix[i][j]=0;
        }
    }
}

1.3对角线相关问题

1.2.1主对角线 & 副对角线

主对角线与副对角线

• 主对角线：从矩阵左上角到右下角的对角线（i = j）
  • 主对角线以上：（i < j）例如（0，2）
  • 主对角线以下：（i > j）例如（3，0）
• 副对角线：从矩阵右上角到左下角的对角线（i + j = n-1）
  • 副对角线以上：（i + j < n-1）例如（0，0）
  • 副对角线以下：（i + j > n-1）例如（3，3）

1.2.3对角线之和

给你一个正方形矩阵 mat，请你返回矩阵对角线元素的和。
请你返回在矩阵主对角线上的元素和副对角线上且不在主对角线上元素的和。

int diagonalSum(vector<vector<int>>& mat) {
    int n = mat.size();  // 正方形矩阵的边长（行数=列数）
    int sum = 0;         // 存储对角线元素总和
    for (int i = 0; i < n; ++i) {
        sum += mat[i][i];// 1. 累加主对角线元素：行号 == 列号（i == i）
        // 2. 累加副对角线元素：行号 + 列号 == n-1（列号 = n-1 - i）
        //    若n为奇数，主副对角线在中心位置（i = n-1 -i → i = (n-1)/2）重合，需跳过
        if (i != n - 1 - i) {
            sum += mat[i][n - 1 - i];
        }
    }

    return sum;
}

1.2.4对角线遍历

列索引为 j ，行索引一定为 k-j
$$0<=i=k-j<m且0<=j<n$$
$由1式：解得【j<=k】且j>k-m即【j>=k-m+1】（整数等价）$
$由2式：解得【j<=n-1】且【j>=0】$

• 当 k 为偶数：从左下到右上遍历（即 j 从 min_j 递增到 max_j）。minj=max(k-m+1,0)
• 当 k 为奇数：从右上到左下遍历（即 j 从 max_j 递减到 min_j）。maxj=min(k,n-1)

vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
    int m=mat.size();
    int n=mat[0].size();
    vector<int> result(m*n);
    result.clear();
    for(int k=0;k<m+n-1;k++){
        int minj=max(k-m+1,0);
        int maxj=min(k,n-1);
        if(k%2==0){
            for(int j=minj;j<=maxj;j++){
                result.push_back(mat[k-j][j]);
            }
        }
        else{
            for(int j=maxj;j>=minj;j--){
                result.push_back(mat[k-j][j]);
            }
        }
    }
    return result;
}

1.3.2按对角线排序

vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
    int m = mat.size();        // 矩阵的行数
    int n = mat[0].size();     // 矩阵的列数
    
    // 使用map存储每条对角线上的元素，key为i-j（对角线标识），value为元素列表
    map<int, vector<int>> diagonals;
    
    // 收集每条对角线上的元素
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            diagonals[i - j].push_back(mat[i][j]);
        }
    }
    
    // 对每条对角线上的元素进行排序
    for (auto& pair : diagonals) {
        sort(pair.second.begin(), pair.second.end());
    }
    
    // 将排序后的元素放回原矩阵
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            // 从对应的对角线中取出元素，使用迭代器跟踪当前位置
            mat[i][j] = diagonals[i - j][0];
            diagonals[i - j].erase(diagonals[i - j].begin());
        }
    }
    
    return mat;
}

1.3.2矩阵中的和

给你一个下标从 0 开始的二维整数数组 nums 。一开始你的分数为 0 。你需要执行以下操作直到矩阵变为空：

• 矩阵中每一行选取最大的一个数，并删除它。如果一行中有多个最大的数，选择任意一个并删除。
• 在步骤 1 删除的所有数字中找到最大的一个数字，将它添加到你的 分数 中。请你返回最后的 分数 。
  

思路：先将矩阵每行按照升序排序，这样每次删除的数就是第一列中的最大元素。

int matrixSum(vector<vector<int>>& nums) {
    int m=nums.size();
    int n=nums[0].size();
    int result=0;
    //每行升序排列
    for(int i=0;i<m;i++){
        sort(nums[i].begin(), nums[i].end());
    }
    //找到每一列的最大值
    for(int j=0;j<n;j++){
        int maxval=0;
        for(int i=0;i<m;i++){
            maxval=max(maxval,nums[i][j]);
        }
        result+=maxval;
    }
    return result;
}

二、矩阵操作

2.1旋转

2.1.1旋转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

class Solution {
public:
    void reverse(vector<int>& nums, int start, int end) {
        while (start < end) {
            swap(nums[start], nums[end]);
            start += 1;
            end -= 1;
        }
    }
    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        reverse(nums, 0, nums.size() - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.size() - 1);
    }
};

2.1.2转置矩阵

矩阵转置的核心是 行与列互换，即原矩阵中位于 (i,j) 位置的元素，转置后会位于 (j,i) 位置。

• 转置后，矩阵的主对角线元素（1、5、9）位置不变（因为 i=j 时，(i,j) 与 (j,i) 是同一个位置）；
• 非对角线元素对称交换，例如 (0,1) 的 2 与 (1,0) 的 4 交换，(0,2) 的 3 与 (2,0) 的 7 交换，(1,2) 的 6 与 (2,1) 的 8 交换。
  

// 填充转置矩阵：原(i,j) → 转置(j,i)
for (int i = 0; i < m; ++i) {
    for (int j = 0; j < n; ++j) {
        transposed[j][i] = matrix[i][j];
    }
}
// 原地转置（仅适用于方阵n×n）。仅遍历上三角区域，避免重复交换（i < j）
for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
        swap(matrix[i][j], matrix[j][i]);// 交换(i,j)和(j,i)
    }
}

2.1.3旋转90度

//顺时针90
for (int i = 0; i < m; ++i) {
    for (int j = 0; j < n; ++j) {
        result[j][m - 1 - i] = matrix[i][j];
    }
}
//逆时针90
for (int i = 0; i < m; ++i) {
    for (int j = 0; j < n; ++j) {
        result[n - 1 - j][i] = matrix[i][j];
    }
}
//旋转180
for (int i = 0; i < m; ++i) {
    for (int j = 0; j < n; ++j) {
        result[m - 1 - i][n - 1 - j] = matrix[i][j];
    }
}

需要注意的是：

• reverse(matrix.begin(), matrix.end())虽然 reverse 操作的是行的顺序，但从列的视角看，每一列的元素确实被上下翻转了。
• 原地旋转：仅适用于方阵（n×n）
• result 新矩阵方法：适用于所有矩阵（方阵 + 非方阵）

// 顺时针旋转90度（原地操作）
void rotate90(vector<vector<int>>& matrix) {
    int n = matrix.size();
    // 步骤1：矩阵转置（行变列）
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            swap(matrix[i][j], matrix[j][i]);
        }
    }
    // 步骤2：翻转每一行
    for (int i = 0; i < n; ++i) {
        reverse(matrix[i].begin(), matrix[i].end());
    }
}
// 逆时针旋转90（顺时针旋转270）
void rotate270(vector<vector<int>>& matrix) {
    int n = matrix.size();
    // 步骤1：矩阵转置
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            swap(matrix[i][j], matrix[j][i]);
        }
    }
    // 步骤2：翻转每一列（上下翻转）
    reverse(matrix.begin(), matrix.end());
}

// 旋转180度
void rotate180(vector<vector<int>>& matrix) {
    int n = matrix.size();
    // 步骤1：翻转每一行
    for (int i = 0; i < n; ++i) {
        reverse(matrix[i].begin(), matrix[i].end());
    }
    // 步骤2：翻转每一列（上下翻转）
    reverse(matrix.begin(), matrix.end());
}

2.1.4循环轮转矩阵

class Solution {
public:
    vector<vector<int>> rotateGrid(vector<vector<int>>& grid, int k) {
        int m = grid.size();    // 矩阵行数（偶数）
        int n = grid[0].size(); // 矩阵列数（偶数）
        int layers = min(m, n) / 2; // 层数（外到内，共min(m,n)/2层）

        // 遍历每一层，单独处理轮转
        for (int layer = 0; layer < layers; ++layer) {
            // 1. 提取当前层的所有元素（按“上→右→下→左”顺序）
            vector<int> layer_elements;
            int top = layer, bottom = m - 1 - layer;  // 当前层的上下边界
            int left = layer, right = n - 1 - layer;  // 当前层的左右边界

            // 上边界：从左到右
            for (int col = left; col <= right; ++col) {
                layer_elements.push_back(grid[top][col]);
            }
            // 右边界：从上到下（跳过已添加的右上角）
            for (int row = top + 1; row <= bottom; ++row) {
                layer_elements.push_back(grid[row][right]);
            }
            // 下边界：从右到左（跳过已添加的右下角）
            for (int col = right - 1; col >= left; --col) {
                layer_elements.push_back(grid[bottom][col]);
            }
            // 左边界：从下到上（跳过已添加的左下角和左上角）
            for (int row = bottom - 1; row >= top + 1; --row) {
                layer_elements.push_back(grid[row][left]);
            }

            // 2. 计算实际需要轮转的次数（k可能很大，取模减少操作）
            int len = layer_elements.size();  // 当前层的元素总数
            int rotate = k % len;             // 实际轮转次数（逆时针轮转rotate次）

            // 3. 将轮转后的元素放回原层位置
            int idx = 0;  // 指向layer_elements中待放回的元素索引
            // 上边界放回
            for (int col = left; col <= right; ++col) {
                // 逆时针轮转rotate次 → 取元素的索引为(rotate + idx) % len
                grid[top][col] = layer_elements[(rotate + idx) % len];
                idx++;
            }
            // 右边界放回
            for (int row = top + 1; row <= bottom; ++row) {
                grid[row][right] = layer_elements[(rotate + idx) % len];
                idx++;
            }
            // 下边界放回
            for (int col = right - 1; col >= left; --col) {
                grid[bottom][col] = layer_elements[(rotate + idx) % len];
                idx++;
            }
            // 左边界放回
            for (int row = bottom - 1; row >= top + 1; --row) {
                grid[row][left] = layer_elements[(rotate + idx) % len];
                idx++;
            }
        }

        return grid;
    }
};

2.2螺旋

2.2.1螺旋矩阵1

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

顺时针螺旋遍历的本质是按照 “右→下→左→上” 的顺序循环遍历，同时不断缩小边界范围，直到所有元素都被访问。

• 边界定义：用top（上边界）、bottom（下边界）、left（左边界）、right（右边界）标记当前未遍历的区域。
• 方向控制：通过direction变量（0 - 右、1 - 下、2 - 左、3 - 上）控制遍历方向，每完成一个方向的遍历就切换方向。
• 边界收缩：每遍历完一个方向后，对应的边界向内收缩（如向右遍历完上边界后，top++将上边界下移）。

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    if(matrix.empty()) return{};
    int left=0;
    int right=matrix[0].size()-1;
    int top=0;
    int bottom=matrix.size()-1;
    // 遍历方向：0-右，1-下，2-左，3-上
    int direction = 0;
    vector<int> result;

    while (top <= bottom && left <= right) {
        if (direction == 0) { // 向右遍历（上边界行）
            for (int col = left; col <= right; ++col) {
                result.push_back(matrix[top][col]);
            }
            top++; // 上边界下移
            direction = 1; // 切换方向为下
        } 
        else if (direction == 1) { // 向下遍历（右边界列）
            for (int row = top; row <= bottom; ++row) {
                result.push_back(matrix[row][right]);
            }
            right--; // 右边界左移
            direction = 2; // 切换方向为左
        } 
        else if (direction == 2) { // 向左遍历（下边界行）
            for (int col = right; col >= left; --col) {
                result.push_back(matrix[bottom][col]);
            }
            bottom--; // 下边界上移
            direction = 3; // 切换方向为上
        } 
        else { // 向上遍历（左边界列）
            for (int row = bottom; row >= top; --row) {
                result.push_back(matrix[row][left]);
            }
            left++; // 左边界右移
            direction = 0; // 切换方向为右
        }
    }
	return result;
}

2.2.2螺旋矩阵2

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

// 当前要填充的数字，从1开始
int num = 1;
// 填充方向：0-右，1-下，2-左，3-上
int direction = 0;
while (num <= n * n) {
    if (direction == 0) { // 向右填充（上边界行）
        for (int col = left; col <= right; ++col) {
            matrix[top][col] = num++;
        }
        top++; // 上边界下移
        direction = 1; // 切换方向为下
    } 
    else if (direction == 1) { // 向下填充（右边界列）
        for (int row = top; row <= bottom; ++row) {
            matrix[row][right] = num++;
        }
        right--; // 右边界左移
        direction = 2; // 切换方向为左
    } 
    else if (direction == 2) { // 向左填充（下边界行）
        for (int col = right; col >= left; --col) {
            matrix[bottom][col] = num++;
        }
        bottom--; // 下边界上移
        direction = 3; // 切换方向为上
    } 
    else { // 向上填充（左边界列）
        for (int row = bottom; row >= top; --row) {
            matrix[row][left] = num++;
        }
        left++; // 左边界右移
        direction = 0; // 切换方向为右
    }
}

2.2.3螺旋矩阵3

在 rows x cols 的网格上，你从单元格 (rStart, cStart) 面朝东面开始。网格的西北角位于第一行第一列，网格的东南角位于最后一行最后一列。
你需要以顺时针按螺旋状行走，访问此网格中的每个位置。每当移动到网格的边界之外时，需要继续在网格之外行走（但稍后可能会返回到网格边界）。最终，我们到过网格的所有 rows x cols 个空间。按照访问顺序返回表示网格位置的坐标列表。

 vector<vector<int>> spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
        vector<vector<int>> result;
        int total = rows * cols;  // 总单元格数量
        
        // 方向数组：东、南、西、北，顺序为顺时针
        vector<vector<int>> dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        
        int dir = 0;  // 当前方向索引，0:东, 1:南, 2:西, 3:北
        int steps = 1; // 当前方向需要走的步数
        int r = rStart, c = cStart; // 当前位置
        
        result.push_back({r, c});  // 加入起始位置
        
        while (result.size() < total) {
            // 每个方向走steps步，东和西各走一次steps，然后steps加1
            for (int i = 0; i < 2; ++i) {
                for (int j = 0; j < steps; ++j) {
                    // 按当前方向移动一步
                    r += dirs[dir][0];
                    c += dirs[dir][1];
                    
                    // 检查是否在网格范围内
                    if (r >= 0 && r < rows && c >= 0 && c < cols) {
                        result.push_back({r, c});
                        // 如果已收集所有单元格，提前返回
                        if (result.size() == total) {
                            return result;
                        }
                    }
                }
                // 切换到下一个方向（顺时针）
                dir = (dir + 1) % 4;
            }
            // 东和西各走steps步后，步数加1
            steps++;
        }
        
        return result;
    }

2.2.4螺旋矩阵4

给你两个整数：m 和 n ，表示矩阵的维数。
另给你一个整数链表的头节点 head 。
请你生成一个大小为 m x n 的螺旋矩阵，矩阵包含链表中的所有整数。链表中的整数从矩阵 左上角 开始、顺时针 按 螺旋 顺序填充。如果还存在剩余的空格，则用 -1 填充。返回生成的矩阵。

vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
    // 初始化m×n矩阵，全部填充为-1
    vector<vector<int>> matrix(m, vector<int>(n, -1));
    //定义边界
    int top=0;
    int bottom=m-1;
    int left=0;
    int right=n-1;
    //
    ListNode* current=head;
    while(current!=nullptr && top <= bottom && left <= right){
            // 1. 从左到右填充上边界
        for (int col = left; col <= right && current != nullptr; col++) {
            matrix[top][col] = current->val;
            current = current->next;
        }
        top++; // 上边界下移，该排已填满
        
        // 2. 从上到下填充右边界
        for (int row = top; row <= bottom && current != nullptr; row++) {
            matrix[row][right] = current->val;
            current = current->next;
        }
        right--; // 右边界左移，该列已填满
        
        // 3. 从右到左填充下边界（需确保还有未填充的行）
        if (top <= bottom) {
            for (int col = right; col >= left && current != nullptr; col--) {
                matrix[bottom][col] = current->val;
                current = current->next;
            }
            bottom--; // 下边界上移，该排已填满
        }
        
        // 4. 从下到上填充左边界（需确保还有未填充的列）
        if (left <= right) {
            for (int row = bottom; row >= top && current != nullptr; row--) {
                matrix[row][left] = current->val;
                current = current->next;
            }
            left++; // 左边界右移，该列已填满
        }
    }
    return matrix;
}

三、搜索【图】

3.3.1最大正方形（LeetCode 221）

在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。

int maximalSquare(vector<vector<char>>& matrix) {
    if (matrix.empty() || matrix[0].empty()) {
        return 0;
    }
    
    int m = matrix.size();
    int n = matrix[0].size();
    int max_side = 0;
    
    // 创建dp数组，dp[i][j]表示以(i,j)为右下角的最大正方形的边长
    vector<vector<int>> dp(m, vector<int>(n, 0));
    
    // 初始化第一行和第一列
    for (int i = 0; i < m; ++i) {
        dp[i][0] = (matrix[i][0] == '1') ? 1 : 0;
        max_side = max(max_side, dp[i][0]);
    }
    
    for (int j = 0; j < n; ++j) {
        dp[0][j] = (matrix[0][j] == '1') ? 1 : 0;
        max_side = max(max_side, dp[0][j]);
    }
    
    // 填充dp数组
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            if (matrix[i][j] == '1') {
                // 状态转移方程：当前位置的最大正方形边长 = 左上角、上方、左方三个位置的最小值 + 1
                dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
                max_side = max(max_side, dp[i][j]);
            } else {
                dp[i][j] = 0;
            }
        }
    }
    
    // 返回最大面积
    return max_side * max_side;
}

3.3.2岛屿数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

// 深度优先搜索：将所有相连的陆地标记为已访问（改为'0'）
void dfs(vector<vector<char>>& grid, int i, int j) {
    int m = grid.size();
    int n = grid[0].size();
    
    // 边界条件：超出网格范围或不是陆地，直接返回
    if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1') {
        return;
    }
    
    // 标记当前陆地为已访问（改为'0'，避免重复访问）
    grid[i][j] = '0';
    
    // 递归访问上下左右四个方向的相邻单元格
    dfs(grid, i - 1, j);  // 上
    dfs(grid, i + 1, j);  // 下
    dfs(grid, i, j - 1);  // 左
    dfs(grid, i, j + 1);  // 右
}
int numIslands(vector<vector<char>>& grid) {
    if (grid.empty() || grid[0].empty()) {
        return 0;
    }
    
    int m = grid.size();
    int n = grid[0].size();
    int count = 0;  // 岛屿数量
    
    // 遍历整个网格
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            // 发现未访问的陆地，开始DFS并计数
            if (grid[i][j] == '1') {
                dfs(grid, i, j);
                count++;
            }
        }
    }
    
    return count;
}

3.3.3腐烂的橘子

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

int orangesRotting(vector<vector<int>>& grid) {
    if (grid.empty() || grid[0].empty()) {
        return 0;
    }
    
    int m = grid.size();
    int n = grid[0].size();
    int fresh = 0;  // 新鲜橘子的数量
    queue<pair<int, int>> q;  // 存储腐烂橘子的位置
    
    // 方向数组：上、下、左、右
    vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    // 初始化：统计新鲜橘子数量并将腐烂橘子加入队列
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == 1) {
                fresh++;
            } else if (grid[i][j] == 2) {
                q.push({i, j});
            }
        }
    }
    
    // 如果没有新鲜橘子，直接返回0
    if (fresh == 0) {
        return 0;
    }
    
    int minutes = 0;  // 记录经过的分钟数
    
    // BFS：逐层扩散腐烂
    while (!q.empty()) {
        int size = q.size();  // 当前层的腐烂橘子数量
        
        // 处理当前层的所有腐烂橘子
        for (int i = 0; i < size; ++i) {
            auto [x, y] = q.front();
            q.pop();
            
            // 检查四个方向的相邻单元格
            for (auto [dx, dy] : dirs) {
                int nx = x + dx;
                int ny = y + dy;
                
                // 检查相邻单元格是否是新鲜橘子
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1) {
                    grid[nx][ny] = 2;  // 感染新鲜橘子
                    fresh--;           // 新鲜橘子数量减少
                    q.push({nx, ny});  // 将新腐烂的橘子加入队列
                }
            }
        }
        
        // 如果队列不为空，说明这一层处理完后还有下一层，时间加1
        if (!q.empty()) {
            minutes++;
        }
    }
    
    // 如果还有新鲜橘子没被感染，返回-1，否则返回所用时间
    return fresh == 0 ? minutes : -1;
}

3.3.4课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    // 构建邻接表表示课程依赖关系
    vector<vector<int>> adj(numCourses);
    // 记录每个课程的入度（即需要先修的课程数量）
    vector<int> inDegree(numCourses, 0);
    
    // 初始化邻接表和入度数组
    for (const auto& pre : prerequisites) {
        int course = pre[0];       // 需要学习的课程
        int prerequisite = pre[1]; // 先修课程
        
        adj[prerequisite].push_back(course); // 先修课程完成后才能学当前课程
        inDegree[course]++;                  // 增加当前课程的入度
    }
    
    // 使用队列存储所有入度为0的课程（可以直接学习的课程）
    queue<int> q;
    for (int i = 0; i < numCourses; ++i) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }
    
    // 记录可以完成的课程数量
    int completed = 0;
    
    // 拓扑排序
    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        completed++;
        
        // 学习完当前课程后，更新其后续课程的入度
        for (int next : adj[curr]) {
            inDegree[next]--;
            // 如果后续课程的入度变为0，说明其所有先修课程都已完成，可以学习
            if (inDegree[next] == 0) {
                q.push(next);
            }
        }
    }
    
    // 如果所有课程都能完成，返回true，否则返回false
    return completed == numCourses;
}