dedecms 我的网站wordpress展示页

【LetMeFly】3200.三角形的最大高度：枚举

力扣题目链接：https://leetcode.cn/problems/maximum-height-of-a-triangle/

给你两个整数 red 和 blue，分别表示红色球和蓝色球的数量。你需要使用这些球来组成一个三角形，满足第 1 行有 1 个球，第 2 行有 2 个球，第 3 行有 3 个球，依此类推。

每一行的球必须是 相同 颜色，且相邻行的颜色必须 不同。

返回可以实现的三角形的 最大 高度。

 

示例 1：

输出： 3

解释：

上图显示了唯一可能的排列方式。

示例 2：

输出： 2

解释：

上图显示了唯一可能的排列方式。

示例 3：

输出： 1

示例 4：

输出： 2

解释：

上图显示了唯一可能的排列方式。

 

提示：

• 1 <= red, blue <= 100

解题方法：枚举

使用一个大小为2的数组记录layer层所需两种颜色分别多少个。

使用layer从1层开始模拟，每次两种颜色分别加上layer。如果球数不足，则停止枚举layer。

• 时间复杂度$O(\min (\sqrt{red},\sqrt{blud}))$，因为$1+2+3+...+k=\frac{n(n+1)}{2}$
• 空间复杂度$O(1)$

AC代码

C++

class Solution {
public:int maxHeightOfTriangle(int red, int blue) {int cnt[2] = {0, 0};int layer = 1;while (true) {cnt[layer % 2] += layer++;if (!((cnt[0] <= red && cnt[1] <= blue) || (cnt[0] <= blue && cnt[1] <= red))) {return layer - 2;}}}
};

Python

class Solution:def maxHeightOfTriangle(self, red: int, blue: int) -> int:cnt = [0, 0]for layer in range(1, 1000000):cnt[layer % 2] += layerif not ((cnt[0] <= red and cnt[1] <= blue) or (cnt[0] <= blue and cnt[1] <= red)):return layer - 1return -1  # Fake Return

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/142967272