题解 | #最大子三角形#

思路：

题目的主要信息：

• 从一个六边形的01矩阵中找到全1的三角形，且要找边长最大的一个
• 其中六边形矩阵的数据以vector数组的形式给出
  
  因为给出的数据是一维的，现在首要的难题的是将一维数组表示的六边形矩阵装入二维矩阵。
  仔细观察边长为的六边形矩阵，一共是行，最长是列。因此我们建立一个这样的矩阵保存数据。因为六边形上下形状的特殊性，对于上半个矩阵的列（下标0开始），元素分布在矩形矩阵的，下半个矩阵因为与上面是对称的，所以可以类似的推断。至此，将一维数组记录的六边形矩阵放入一个二维矩阵中，二维数组中空出来的格子用0填充，反正我们后续只计算有1的格子。

方法一：动态规划
具体做法：
有了记录六边形的二位数组，接下我们考虑的我们找到最大三角形。因为正三角形和正六边形的对称性，我们找到的三角形会有三个角的朝向，但是任意一个都会朝向上或者下。因为我们只考虑三角形朝上或者朝下，且观察我们会发现朝上和朝下是分开的，可能出现边长不一样的情况，所以要分开讨论。

我们以一个二维数组tri记录小三角形的朝上（1）或是朝下（0）。
只考虑朝上的情况。如果我们找到一个三角形为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)); //dp[i][j] 记录以 matrix[i][j]为顶端的三角形的边长最大值
        int count = 0;
        int res = 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[count++];
                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[count++];
                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;
                    //除去最下一行、最左右两边、朝向向下、下方一个不为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; //等于其左下角加上右下角为首的三角形的较小值再加1
                    res = max(res, 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;//等于其左上角加上右上角为首的三角形的较小值再加1
                    res = max(res, dp[i][j]);//维护最大值
                }
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，其中为六边形边长，四次循环都是遍历矩阵，而矩阵的边长分别是与
• 空间复杂度：，三个辅助的二维矩阵

方法二：直接迭代
具体做法：
动态规划的缺点在于使用三个的空间，其实我们也可以直接迭代，不使用这三个空间解决问题。
首先，对于matrix数组，我们知道若是在上半个矩阵的第(从0开始）行，那么该行六边形一共有个元素，如果在下半个矩阵的第（从开始）行，那么该行六边形的也有，有了这个数据我们可以设置一个index直接访问数组maps，不用再拿二维矩阵来装六边形。
再来，对于tri数组，我们可以发现在上半个矩阵，首元素是朝上的三角形，在下半个矩阵，首元素朝下。因此我们也可以在通过index访问maps的时候再判断小三角形的朝向。
最后，对于dp数组，其实整个矩阵保存的除了0就是1，我们完全可以把这些1当成dp数组来使用，将原本dp应该得到的结果直接加到，比如maps[index]就记录index（某行某列）这个朝下的元素，以它为顶部的子三角形最大多少，到时候我们不判断0与1，直接判断非0与否。而且它对于它反向的三角形没有影响（反向我们也只判断非0与否，不会看数字大小具体多少），因此可以随意修改。
最后按照方法一，顺序访问maps数组，只能找到朝下的最大子三角形，因此我们还需要将数组maps逆转，再求一次朝上的最大子三角形。

class Solution {
public:
    int largestSubUpperTriangle(int a, vector<int> &maps){ //找到最大的朝下的三角形
        int index = 0;
        int res = 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]); //左右上角
                    res = max(res, 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]);
                    }
                    res = max(res, maps[index]);
                }
                index++;
            }
        }
        return res;
    }
    int largestSubTriangle(int a, vector<int>& maps) {
        int res = 0;
        res = max(res, largestSubUpperTriangle(a, maps)); //朝下的三角形
        reverse(maps.begin(), maps.end()); //逆转数据
        res = max(res, largestSubUpperTriangle(a, maps)); //朝上的三角形
        return res;
    }
};

复杂度分析：

• 时间复杂度：，设，我们访问最多遍历整个六边形即给出的这个一维数组
• 空间复杂度：，无额外空间