221最大正方形

深藏阁楼爱情的钟 2023-02-28 15:26 16阅读 0赞

## 一、前言 ##

标签：动态规划、栈运用、双指针。

问题来源LeetCode 5 难度：中等。

问题链接：[https://leetcode-cn.com/problems/longest-palindromic-substring/][https_leetcode-cn.com_problems_longest-palindromic-substring]

## 二、题目 ##

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

**示例：**

输入: 
    1 0 1 0 0
    1 0 1 1 1
    1 1 1 1 1
    1 0 0 1 0
    输出: 4

## 三、思路 ##

动态规划解决这个问题，递推公式：

1.  dp(i,j) = 1 （i == 0 || j == 0）
2.  dp(i,j) = min(dp(i−1,j), dp(i−1,j−1), dp(i,j−1)) + 1

**复杂度分析**：时间复杂度O(m\*n)，空间复杂度O(m\*n)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70][]

## 四、编码实现 ##

//==========================================================================
    /*
    * @file    : 221_MaximalSquare.h
    * @label   : 动态规划
    * @blogs   : https://blog.csdn.net/nie2314550441/article/details/107498710
    * @author  : niebingyu
    * @date    : 2020/07/21
    * @title   : 221.最大正方形
    * @purpose : 在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
    *
    * 示例1：
    * 输入:
    * 1 0 1 0 0
    * 1 0 1 1 1
    * 1 1 1 1 1
    * 1 0 0 1 0
    *
    * 输出: 4
    *
    * 来源：力扣（LeetCode）
    * 难度：中等
    * 链接：https://leetcode-cn.com/problems/maximal-square/
    */
    //==========================================================================
    #pragma once
    #include <iostream>
    #include <vector>
    #include <unordered_map>
    #include <algorithm>
    #include <assert.h>
    using namespace std;
    
    #define NAMESPACE_MAXIMALSQUARE namespace NAME_MAXIMALSQUARE {
    #define NAMESPACE_MAXIMALSQUAREEND }
    NAMESPACE_MAXIMALSQUARE
    
    // 动态规划
    // dp(i,j) = min(dp(i−1,j), dp(i−1,j−1), dp(i,j−1)) + 1
    class Solution 
    {
    public:
        int maximalSquare(vector<vector<char>>& matrix) 
        {
            if (matrix.size() == 0 || matrix[0].size() == 0) 
                return 0;
            
            int maxSide = 0;
            int rows = matrix.size(), columns = matrix[0].size();
            vector<vector<int>> dp(rows, vector<int>(columns));
            for (int i = 0; i < rows; i++)
            {
                for (int j = 0; j < columns; j++) 
                {
                    if (matrix[i][j] == '1') 
                    {
                        if (i == 0 || j == 0) 
                            dp[i][j] = 1;
                        else
                            dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                        
                        maxSide = max(maxSide, dp[i][j]);
                    }
                }
            }
    
            int maxSquare = maxSide * maxSide;
            return maxSquare;
        }
    };
    
    以下为测试代码//
    // 测试 用例 START
    void test(const char* testName, vector<vector<char>>& matrix, int expect)
    {
        Solution s;
        int result = s.maximalSquare(matrix);
    
        if (result == expect)
            cout << testName << ", solution passed." << endl;
        else
            cout << testName << ", solution failed. " << endl;
    }
    
    // 测试用例
    void Test1()
    {
        vector<vector<char>> matrix = 
        {
            { '1', '0', '1', '0', '0' },
            { '1', '0', '1', '1', '1' },
            { '1', '1', '1', '1', '1' },
            { '1', '0', '0', '1', '0' }
    	};
        int expect = 4;
        test("Test1()", matrix, expect);
    }
    
    NAMESPACE_MAXIMALSQUAREEND
    // 测试 用例 END
    //
    void MaximalSquare_Test()
    {
        cout << "------ start 221.最大正方形 ------" << endl;
        NAME_MAXIMALSQUARE::Test1();
        cout << "------ end 221.最大正方形 --------" << endl;
    }

**执行结果：**

![20200721210312522.png][]

[https_leetcode-cn.com_problems_longest-palindromic-substring]: https://leetcode-cn.com/problems/longest-palindromic-substring/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70]: /images/20230209/8c6187987a3c48f4adf14d4f106573e1.png
[20200721210312522.png]: https://img-blog.csdnimg.cn/20200721210312522.png