题意

给你一个边长为 a 的六边形 01 矩阵，请找到一个最大的全 1 子三角形，输出三角形的边长 b。
图片说明

题解

想法一

通过观察我们可以了解到，只有两种三角形：一种是尖头朝上的，一种是朝下的。
我们可以只处理尖头向下的三角形，然后把整个图反过来一次，我们就可以求得尖头朝上的三角形了。所以剩下的问题就是，我们如何求出所有头朝下的子三角形。

想法二

首先我们需要弄清楚的是，这个子三角形需要如何进行表示。难道是把这个三角形的所有元素都一一列举出来么？当然这是一个可行的方案，但是那样的开销巨大，最坏的情况下，我们几乎需要把整个地图的大部分元素都存储起来才可以描述一个三角形的具体样子。这显然是不可取的。对于一个三角形，描述它的最好方法就是描述它的三个顶点分别在什么地方，这是不容置疑的。而对于我们这道坐标格十分工整的题目来说，描述一个三角形的方法又简单了很多。我们只需要知道一个顶点，以及边长就可以确定这个三角形了！

想法三

每个三角形对应了地图中的一个编号，比如编号i就可以代表一个小三角形。要描述一个大三角形，只需要加上另一个维度len，表示三角形的边长。在这里，因为我们只关心最大的子三角形，所以只需要保留每个小三角形开始的最大的len就好了，这个显然是唯一的。我们将以每个三角形为顶点，存在的三角形的最大边长记为maxlen，这个和编号一一对应。所以我们选择使用一个数组来进行表示。

如果要求尖头朝下的三角形，那么我们可以选择对于每个尖头朝下的小三角形，求出以它为三角形的尖头，这个大三角形最大可以是多少，这个也就是我们定义的maxlen。幸运的是，这个可以通过动态规划的方式进行转移。方程式就是 maxlen[i] = min(maxlen[i的左上], maxlen[i的右上]) * map[i] * map[i的正上方] + map[i]; 所以问题的关键就是就是求左上，右上，正上方的坐标编号。

想法四

坐标的编号。。。需要仔细数一数就好啦。
图片说明
这个坐标转换带来的难度主要是代码实现上的。在思路上并没有太大的难度。在这里，为了方便起见，我选择将六边形的上半部分和下半部分进行拆开处理。然后再将上半部分按照行进行展开。比如上图中，为什么8的正上方是2，左上方是1，右上方是3呢？其实主要就是寻找8的正上方是什么。

观察可以发现，6的上面是0，8的上方是2，10的上方是4，所以对于第一行和第二行，这样紧邻的上下小三角形的编号差都是6，这样的规律是可以推广的。比如对称的，倒数第一行和倒数第二行的编号差也是6。而上下交界处的差值又变成了7，我们可以一行一行的处理，把这些编号的差值计算出来， 那么也就很容易通过编号寻找到每个下三角行上方的编号啦。

代码

class Solution {
public:
    /**
     * 计算六边形01矩阵中最大的全1子三角形的边长
     * @param a int整型无类型 六边形01矩阵的边长
     * @param maps int整型vector 矩阵的具体数据，从上到下，从左到右顺次排列
     * @return int整型无类型
     */
    int largestSubUpperTriangle(int a, vector<int> &maps) {
        int ptr = 0, ans = 0;
        for (int i = 0; i < a; i++) {
            int len = 2 * (a + i) + 1;
            for (int j = 0; j < len; j++) {
                if (j & 1) {
                    if (j > 1 && j < len - 2 && i != 0) {
                        maps[ptr] = (maps[ptr] && maps[ptr - len + 1] ? 
                            1 + min(maps[ptr - len + 2], maps[ptr - len]) : maps[ptr]);
                    }
                    ans = max(ans, maps[ptr]);
                }
                ptr++;
            }
        }
        for (int i = a - 1; i >= 0; i--) {
            int len = 2 * (a + i) + 1;
            for (int j = 0; j < len; j++) {
                if (j & 1 ^ 1) {
                    if (i == a - 1) {
                        if (j > 0 && j < len - 1) {
                            maps[ptr] = (maps[ptr] && maps[ptr - len] ?
                                1 + min(maps[ptr - len - 1], maps[ptr - len + 1]) : maps[ptr]);
                        }
                    } else {
                        maps[ptr] = (maps[ptr] && maps[ptr - len - 1] ?
                            1 + min(maps[ptr - len - 2], maps[ptr - len]) : maps[ptr]);
                    }
                    ans = max(ans, maps[ptr]);
                }
                ptr++;
            }
        }
        return ans;
    }
    int largestSubTriangle(int a, vector<int> maps)
    {
        // write code here
        int ans = 0;
        ans = std::max(ans, largestSubUpperTriangle(a, maps));
        reverse(maps.begin(), maps.end());
        ans = std::max(ans, largestSubUpperTriangle(a, maps));
        return ans;
    }
};