思路：
题目的主要信息：
- 从一个六边形的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;
}
};复杂度分析：
- 时间复杂度：
，设
，我们访问最多遍历整个六边形即给出的这个一维数组
- 空间复杂度：
，无额外空间
京公网安备 11010502036488号