最大子三角形

[编程题]最大子三角形

热度指数：1278 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

示例1

输入

2,[0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1]

输出

说明

如下图，可以找到一个边长为2的子三角形，但并不唯一。

备注:

对于所有的输入数据，满足 。

描述这个六边形 01 矩阵 maps 的数组下标，每个数字依次从左到右，再从上到下对应每一个区域。详见下图：

算法知识视频讲解

Anoxiacxy

发表于 2020-02-05 12:09:38

题意给你一个边长为 a 的六边形 01 矩阵，请找到一个最大的全 1 子三角形，输出三角形的边长 b。题解想法一通过观察我们可以了解到，只有两种三角形：一种是尖头朝上的，一种是朝下的。我们可以只处理尖头向下的三角形，然后把整个图反过来一次，我们就可以求得尖头朝上的三角形了。所以剩下的问题就展开全文

摸鱼学大师

发表于 2021-07-29 21:53:46

思路：题目的主要信息：从一个六边形的01矩阵中找到全1的三角形，且要找边长最大的一个其中六边形矩阵的数据以vector数组的形式给出因为给出的数据是一维的，现在首要的难题的是将一维数组表示的六边形矩阵装入二维矩阵。仔细观察边长为的六边形矩阵，一共是行，最长是列。因此我们建立一个这样的矩阵保存展开全文

认认真真coding

发表于 2021-07-31 11:08:59

题目描述给你一个边长为 a 的六边形 01 矩阵，请找到一个最大的全1子三角形，输出三角形的边长b。方法一：动态规划方法求解思路对于本题目要求解最大的全1子三角形，因为题目给出的数据，为了方便题目的求解，我们将一维数组表示的六边形矩阵装入二维矩阵。根据边长为a的六边形矩阵，共有2a行，最长4a- 展开全文