1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92  // @Title: 最大正方形 (Maximal Square) // @Author: 15816537946@163.com // @Date: 2019-10-16 22:11:54 // @Runtime: 4 ms // @Memory: 4.2 MB /* * @lc app=leetcode.cn id=221 lang=golang * * [221] 最大正方形 * * https://leetcode-cn.com/problems/maximal-square/description/ * * algorithms * Medium (38.18%) * Likes: 131 * Dislikes: 0 * Total Accepted: 11.4K * Total Submissions: 29.7K * Testcase Example: '[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]' * * 在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。 * * 示例: * * 输入: * * 1 0 1 0 0 * 1 0 1 1 1 * 1 1 1 1 1 * 1 0 0 1 0 * * 输出: 4 * */ func maximalSquare(matrix [][]byte) int { m := len(matrix) if m == 0 { return 0 } n := len(matrix[0]) if n == 0 { return 0 } var maxEdage int dp := make([][]int, m) for i := 0; i < m; i++ { dp[i] = make([]int, n) if matrix[i][0] == '1' { dp[i][0] = 1 maxEdage = 1 } } for i := 0; i < n; i++ { if matrix[0][i] == '1' { dp[0][i] = 1 maxEdage = 1 } } for i := 1; i < m; i++ { for j := 1; j < n; j++ { if matrix[i][j] == '1' { dp[i][j] = 1 + min( dp[i-1][j-1], min( dp[i-1][j], dp[i][j-1], ), ) maxEdage = max(dp[i][j], maxEdage) } } } return maxEdage * maxEdage } func max(a, b int) int { if a > b { return a } return b } func min(a, b int) int { if a > b { return b } return a }