题解 | #最大子三角形#

题目描述
给你一个边长为 a 的六边形 01 矩阵，请找到一个最大的全1子三角形，输出三角形的边长b。

方法一：动态规划方法

求解思路
对于本题目要求解最大的全1子三角形，因为题目给出的数据，为了方便题目的求解，我们将一维数组表示的六边形矩阵装入二维矩阵。根据边长为a的六边形矩阵，共有2a行，最长4a-1列。我们将其元素放在矩形矩阵的[a-i-1,3a+i-1]中，并且我们根据正六边形的对称性，我们选定其一个朝向，并且用dp[i][j]记录以矩形矩阵中某一个点为顶点的三角形边长的最大值。根据图形的特点我们有状态转移方程：dp[i][j]=min{dp[i+1][j-1],dp[i+1][j+1]}+1.最后根据上述的思路即可得到本题的答案。

图片说明

解题代码

class Solution {
public:
    int largestSubTriangle(int a, vector<int>& maps) {
        int n = 4 * a - 1;
        vector<vector<int> > matrix(2 * a, vector<int>(n, 0)); // 覆盖六边形的矩阵
        vector<vector<int> > tri(2 * a, vector<int>(n, 0)); // 三角形方向
        vector<vector<int> > dp(2 * a, vector<int>(n, 0));
        int hycount = 0;
        int hyres = 0;
        for(int i = 0, k = 1; i < a; i++)
        {   //遍历上半矩阵
            for(int j = a - i - 1; j < 3 * a + i; j++) 
            {
                matrix[i][j] = maps[hycount++];
                tri[i][j] = k % 2; // 上半个六边形每行奇数朝上
                k++;
            }
            k = 1;
        }
        for(int i = a - 1, k = 0; i >= 0; i--)
        {   //遍历下半矩阵
            for(int j = a - 1 - i; j < 3 * a + i; j++)
            {
                matrix[2 * a - i - 1][j] = maps[hycount++];
                tri[2 * a - i - 1][j] = k % 2; // 下半个六边形每行偶数朝上
                k++;
            }
            k = 0;
        }
        for(int i = 2 * a - 1; i >= 0; i--)
        {   //找朝上的最大三角形
            for(int j = n - 1; j >= 0; j--)
            {
                if(matrix[i][j] == 1)
                {
                    dp[i][j] = 1;
                    if(i < 2 * a - 1 && j < n - 1 && j > 0 && tri[i][j] == 1 && dp[i + 1][j] == 1) 
                        dp[i][j] = min(dp[i + 1][j - 1], dp[i + 1][j + 1]) + 1;
                    hyres = max(hyres, dp[i][j]); // 维护最大值
                }
            }
        }
        for(int i = 0; i < 2 * a; i++)
        {   //找朝下的最大三角形
            for(int j = 0; j < n; j++)
            {
                if(matrix[i][j] == 1)
                {
                    dp[i][j] = 1;
                     //除去最上一行、最左右两边、朝向向上、上方一个不为1，这四种情况不能为顶部三角，继续添加
                    if(i > 0 && j < n - 1 && j > 0 && tri[i][j] == 0 && dp[i - 1][j] == 1) 
                        dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j + 1]) + 1;
                    hyres = max(hyres, dp[i][j]); // 更新最大值
                }
            }
        }
        return hyres; // 返回结果
    }
};

复杂度分析
时间复杂度：遍历矩形矩阵，两层循环，因此时间复杂度为 $O$ ( $图片说明$ )
空间复杂度：引入辅助二维数组，因此空间复杂度为 $O$ ( $图片说明$ )

方法二：基于动态规划的优化方法

求解思路
对于方法一，我们考虑在不引入多余的二维数组的情况下对问题进行求解。对于矩形矩阵，我们对于上半矩阵的第i行，那么该行六边形共有2*(a+i)+1个元素，同理下半行也是如此。因此我们设置一个index直接访问数组，不用像方法一中使用二维矩阵来存储。综上，其余根据方法一的做法，即可求得本题的答案。

图片说明

解题代码

class Solution {
public:
    //
    int largestSubUpperTriangle(int a, vector<int> &maps)
    {   //找到最大的朝下的三角形
        int index = 0; // 引入index对本题的解法进行优化
        int hyres = 0; // 记录结果
        for (int i = 0; i < a; i++) 
        {   //遍历上半个六边形
            int n = 2 * (a + i) + 1; // 该行长度
            for (int j = 0; j < n; j++) 
            {
                if (j % 2 == 1) 
                {   //只找朝下的小三角形
                    if (j > 1 && j < n - 2 && i != 0) // 不在边界
                        maps[index] = (maps[index] && maps[index - n + 1] ? 1 + min(maps[index - n + 2], maps[index - n]) : maps[index]);
                    hyres = max(hyres, maps[index]);
                }
                index++;
            }
        }
        for (int i = a - 1; i >= 0; i--) 
        {   //遍历下半个六边形
            int n = 2 * (a + i) + 1; // 该行长度
            for (int j = 0; j < n; j++)
            {
                if (j % 2 == 0) 
                {   //只找朝下的小三角形
                    if (i == a - 1)
                    {   //两种情况，与方法一这里对应下半个矩阵从a-1开始
                        if (j > 0 && j < n - 1) // 不在边界
                            maps[index] = (maps[index] && maps[index - n] ? 1 + min(maps[index - n - 1], maps[index - n + 1]) : maps[index]);
                    }
                    else
                    {
                        maps[index] = (maps[index] && maps[index - n - 1] ? 1 + min(maps[index - n - 2], maps[index - n]) : maps[index]);
                    }
                    hyres = max(hyres, maps[index]);
                }
                index++;
            }
        }
        return hyres;
    }
    int largestSubTriangle(int a, vector<int>& maps) {
        int hyres = 0; // 存储结果
        hyres = max(hyres, largestSubUpperTriangle(a, maps)); // 朝下的三角形
        reverse(maps.begin(), maps.end()); // 逆转数据
        hyres = max(hyres, largestSubUpperTriangle(a, maps)); // 朝上的三角形
        return hyres; // 返回结果
    }
};

复杂度分析
时间复杂度：两层循环，因此时间复杂度为 $图片说明$
空间复杂度：没有引入额外的内存地址空间，因此空间复杂度为 $O(1)$