leetcode力扣刷题系列——【三角形的最大高度】

题目

给你两个整数 red 和 blue，分别表示红色球和蓝色球的数量。你需要使用这些球来组成一个三角形，满足第 1 行有 1 个球，第 2 行有 2 个球，第 3 行有 3 个球，依此类推。
每一行的球必须是 相同 颜色，且相邻行的颜色必须 不同。
返回可以实现的三角形的 最大 高度。

示例 1：
输入：
red = 2, blue = 4
输出：
3

示例 2：
输入：
red = 2, blue = 1
输出：
2

示例 3：
输入：
red = 1, blue = 1
输出：
1

示例 4：
输入：
red = 10, blue = 1
输出：
2

提示：
1 <= red, blue <= 100

答案

我的方法
我的方法思路非常简单，我们既然要让他拼成一个三角形，且是每一行的颜色都不一样，那么第一行要么蓝色要么红色，只要确定了第一行的颜色，后面的就都确定了，我分别让红色、蓝色作为第一行，各自求出一个高度，然后我们在将两个高度进行比较后输出，就能得到最好的结果。
这个方法的时间复杂度为O(n)

class Solution:def maxHeightOfTriangle(self, red: int, blue: int) -> int:high1=0high2=0red1=redblue1=bluefor i in range(red1+blue1):if i%2==0:#红先放置red1=red1-1-iif red1>=0 and blue1>=0:high1+=1else:blue1=blue1-i-1if blue1>=0 and red1>=0:high1+=1for i in range(red+blue):if i%2==0:#蓝先放置blue=blue-i-1if blue>=0 and red>=0:high2+=1else:red=red-1-iif red>=0 and blue>=0:high2+=1if high1>=high2:return high1else:return high2

官方的方法一 —— 枚举高度
官方的方法一跟我的方法很像，虽然我也不知道自己用的是枚举法，但是官方说是那我就是。

思路与算法
我们可以递增地枚举三角形的高度，在第 i 行时，如果对应的颜色的剩余球数大于等于 i 个，那么就可以组成第 i 行，否则不能，三角形的最大高度为 i−1。
三角形的颜色布局有两种可能：即红蓝交替（第一行为红色）或者蓝红交替（第一行为蓝色），我们分别枚举这两种情况，并取二者高度的较大值即可。

class Solution:def maxHeightOfTriangle(self, red: int, blue: int) -> int:def maxHeight(x: int, y: int) -> int:i = 1while True:if i % 2 == 1:x -= iif x < 0:return i - 1else:y -= iif y < 0:return i - 1i += 1return max(maxHeight(red, blue), maxHeight(blue, red))

官方的方法二 —— 直接计算出高度

思路与算法
我们也可以使用等差数列公式直接计算出高度。
对于从第一行开始的情况，球的个数依次为 1,3,5,⋯,2k−1，其中 2k−1 是最后一行，那么总计个数为：
1+3+5+⋯+(2k−1)=[(1+(2k−1))×k]/2 =k^2
那么 k 的最大值即为 ⌊no⌋，其中no是提供给奇数行的球的数量，⌊⋅⌋ 表示向下取整。
同理，对于从第二行开始的情况，有：
2+4+6+⋯+2k=[(2+2k)×k]/2 =k^2+k
解方程可得 k 的最大值为 ⌊ [−1+ (1+4ne)^(1/2)]/2⌋，其中ne是提供给偶数行的球的数量。
因此最后一个奇数行为 2⌊no⌋−1，最后一个偶数行为 2⌊ [−1+ (1+4ne)^(1/2)]/2⌋，最终的答案即为其中的较小值加 1。

 def maxHeight(x: int, y: int) -> int:odd = 2 * int(sqrt(x)) - 1even = 2 * int((-1 + sqrt(1 + 4 * y)) / 2)return min(odd, even) + 1return max(maxHeight(red, blue), maxHeight(blue, red))

作者：力扣官方题解
链接在这里
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。