2025-01-28：三角形的最大高度。给定两个整数 red 和 blue，代表红色球和蓝色球的数量，我们希望用这些球构建一个三

福大大架构师每日一题

发布于 2025-02-05 14:04:40

4800

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

2025-01-28：三角形的最大高度。给定两个整数 red 和 blue，代表红色球和蓝色球的数量，我们希望用这些球构建一个三角形。

三角形的结构是这样的：第一行有 1 个球，第二行有 2 个球，第三行有 3 个球，依此类推。

在构建过程中，要求每一行的球必须是同一种颜色，并且相邻两行的颜色必须不同。

目标是计算可以构造的最大三角形高度。

输入： red = 2, blue = 4。

输出： 3。

解释：

blue

red red

blue blue blue。

答案2025-01-28：

chatgpt[1]

题目来自leetcode3200。

大体步骤如下：

1.计算红球对应的高度 odd：

• 假设红球数量为 x，三角形的高度 odd 可以计算为奇数行的球总数。根据题目给出的结构，第一行 1 个球，第二行 3 个球，第三行 5 个球，依此类推。所以奇数行球的数量可以通过公式 2 * sqrt(x) - 1 求得。

2.计算蓝球对应的高度 even：

• 假设蓝球数量为 y，三角形的高度 even 可以计算为偶数行的球总数。根据题目给出的结构，第一行 2 个球，第二行 4 个球，第三行 6 个球，依此类推。偶数行球的数量可以通过公式 2 * ((-1 + sqrt(1 + 4*y)) / 2) 求得。

3.返回最大高度：

• 返回奇数高度 odd 和偶数高度 even 中的较小值加 1，即返回最终的最大高度。

总的时间复杂度是 O(1)，因为所有的计算都是基于输入红色和蓝色球的数量进行简单的数学运算，而没有任何循环或递归操作。

总的额外空间复杂度也是 O(1)，因为除了输入值红色和蓝色球的数量之外，我们只使用了一些变量来存储计算中间结果，并没有占用额外空间。

Go完整代码如下：

package main

import (
    "fmt"
    "math"
)

func maxHeightOfTriangle(red int, blue int)int {
    return max(maxHeight(red, blue), maxHeight(blue, red))
}

func maxHeight(x, y int)int {
    odd := 2*int(math.Sqrt(float64(x))) - 1
    even := 2 * int((-1+math.Sqrt(1+4*float64(y)))/2)
    return min(odd, even) + 1
}

func main() {
    red := 2
    blue := 4
    result := maxHeightOfTriangle(red, blue)
    fmt.Println(result)
}

Rust完整代码如下：

use std::cmp;

fnmain() {
    letred = 2;
    letblue = 4;
    letresult = max_height_of_triangle(red, blue);
    println!("{}", result);
}

fnmax_height_of_triangle(red: i32, blue: i32) ->i32 {
    cmp::max(max_height(red, blue), max_height(blue, red))
}

fnmax_height(x: i32, y: i32) ->i32 {
    letodd = 2 * ((x asf64).sqrt() asi32) - 1;
    leteven = 2 * (((-1.0 + (1.0 + 4.0 * (y asf64)).sqrt()) / 2.0) asi32);
    cmp::min(odd, even) + 1
}

Python完整代码如下：

# -*-coding:utf-8-*-

import math

defmax_height_of_triangle(red: int, blue: int) -> int:
    returnmax(max_height(red, blue), max_height(blue, red))

defmax_height(x: int, y: int) -> int:
    odd = 2 * int(math.sqrt(x)) - 1
    even = 2 * int((-1 + math.sqrt(1 + 4 * y)) / 2)
    returnmin(odd, even) + 1

defmain():
    red = 2
    blue = 4
    result = max_height_of_triangle(red, blue)
    print(result)

if __name__ == "__main__":
    main()