算法每日一练 (23)

💢欢迎来到张翊尘的技术站
💥技术如江河，汇聚众志成。代码似星辰，照亮行征程。开源精神长，传承永不忘。携手共前行，未来更辉煌💥

官方站点： 力扣 Leetcode

算法每日一练 (23)

最大正方形

题目地址：最大正方形

题目描述

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

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

示例 2：

输入：matrix = [["0","1"],["1","0"]]
输出：1

示例 3：

输入：matrix = [["0"]]
输出：0

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] 为 '0' 或 '1'

解题思路

• 首先创建辅助变量：m、n、maxVal、dp：

  • m 和 n 分别表示矩阵的行数和列数。
  • maxVal 用于记录矩阵中最大的正方形边长，初始值为 0。
  • dp 用于记录当前行的正方形边长。

• 紧接着，遍历矩阵的第一行，更新 maxVal 和 dp[i] 的值。这是因为第一行中的每个 '1' 都可以构成一个边长为 1 的正方形。

• 从第二行开始，遍历矩阵的每个位置 (i, j)，对于每一行的每个元素：

  • 如果是第一列（j == 0），直接将当前元素的值赋给 dp[j] 即可。
  • 否则，根据动态规划的逻辑更新 dp[j]：
    • 如果当前元素是 '0'，则 dp[j] 为 0，因为无法形成正方形。
    • 如果当前元素是 '1'，则 dp[j] 的值为：当前元素的上方（up）、左方（left）和左上方（lup）三个值的最小值加 1。这是因为正方形的形成需要依赖于其上方、左方和左上方的正方形边长。

• 更新 maxVal 为当前列的最大值。

• 最终返回 maxVal 的平方，即是满足题意的返回值。

解题代码

c/c++

#include <vector>class Solution
{
public:int maximalSquare(std::vector<std::vector<char>> &matrix){int m = matrix.size();int n = matrix[0].size();int maxVal = 0;std::vector<int> dp(n, 0);for (int i = 0; i < n; i++){dp[i] = matrix[0][i] - '0';maxVal = std::max(maxVal, dp[i]);}for (int i = 1; i < m; i++){int prev = dp[0];for (int j = 0; j < n; j++){int cur = matrix[i][j] - '0';if (j == 0)dp[j] = cur;else{int t = dp[j];if (matrix[i][j] == '0')dp[j] = 0;else{int up = t;int left = dp[j - 1];int lup = prev;dp[j] = std::min(std::min(up, left), lup) + 1;}prev = t;}maxVal = std::max(maxVal, dp[j]);}}return maxVal * maxVal;}
};

golang

func maximalSquare(matrix [][]byte) int {m := len(matrix)n := len(matrix[0])maxVal := 0dp := make([]int, n)for i := 0; i < n; i++ {dp[i] = int(matrix[0][i] - '0')maxVal = max(maxVal, dp[i])}for i := 1; i < m; i++ {prev := dp[0]for j := 0; j < n; j++ {cur := int(matrix[i][j] - '0')if j == 0 {dp[j] = cur} else {t := dp[j]if matrix[i][j] == '0' {dp[j] = 0} else {up, left, lup := t, dp[j-1], prevdp[j] = min(up, left, lup) + 1}prev = t}maxVal = max(maxVal, dp[j])}}return maxVal * maxVal
}

lua

local function maximalSquare(matrix)local m, n = #matrix, #matrix[1]local maxVal = 0local dp = {}for i = 1, n dodp[i] = matrix[1][i] - '0'maxVal = math.max(maxVal, dp[i])endfor i = 2, m dolocal prev = dp[1]for j = 1, n dolocal cur = matrix[i][j] - '0'if j == 1 thendp[j] = curelselocal t = dp[j]if matrix[i][j] == '0' thendp[j] = 0elselocal up, left, lup = t, dp[j - 1], prevdp[j] = math.min(up, left, lup) + 1endprev = tendmaxVal = math.max(maxVal, dp[j])endendreturn maxVal * maxVal
end

🌺🌺🌺撒花！

如果本文对你有帮助，就点关注或者留个👍
如果您有任何技术问题或者需要更多其他的内容，请随时向我提问。