三角形的最大高度

2024-10-15

题目:

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

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

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

示例 1:

输入: red = 2, blue = 4

输出: 3

解释:

img

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

示例 2:

输入: red = 2, blue = 1

输出: 2

解释:

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

示例 3:

输入: red = 1, blue = 1

输出: 1

示例 4:

输入: red = 10, blue = 1

输出: 2

解释:

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

提示:

  • 1 <= red, blue <= 100

思路:

	我们只需要模拟就行了,一层层的加,直到不满足了,就返回上一个高度就行了,什么情况下不满足呢,那就是目前积累的最多的颜色的球数目大于最大的,或者积累的少的球数目大于第二大的,我们就返回上一层就好了。

代码:

class Solution {
public:
    // 函数用于计算给定红色和蓝色单位时,可以构建的最大高度的三角形
    int maxHeightOfTriangle(int red, int blue) {
        // 获取较大和较小的单位数
        int maxV = max(red, blue); // maxV 用于存储较大的单位数
        int minV = min(red, blue); // minV 用于存储较小的单位数

        int h = 1;   // 初始化高度 h,从 1 开始
        int first = 0;   // first 用于记录奇数层的总单位数
        int second = 0;  // second 用于记录偶数层的总单位数

        // 开始循环,每次增加一层高度
        while(true) {
            if(h % 2 == 1) {
                // 如果当前层为奇数层,增加到 first
                first += h;
            } else {
                // 如果当前层为偶数层,增加到 second
                second += h;
            }

            // 如果当前任何一个累积数超过了可用的最大或最小单位数,结束
            if(max(first, second) > maxV || min(first, second) > minV) {
                return h - 1;  // 返回前一层的高度,因为当前层无法完成
            }

            h++;  // 继续增加高度
        }

        // 理论上不会到达此处,但为了保险起见,返回 1
        return 1;
    }
};