Easy

题目描述

给你两个整数 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

提示：

  • 计算两种可能性的最大高度。即红球在顶部和蓝球在顶部。
  • 为了计算最大高度，使用简单的 for 循环并删除此级别所需的球数。

解题思路

这道题的核心思路是模拟两种情况下构建三角形的过程。

分析思路： 由于相邻行必须使用不同颜色的球，我们可以分两种情况考虑：

  1. 第1行使用红球开始（奇数行用红球，偶数行用蓝球）
  2. 第1行使用蓝球开始（奇数行用蓝球，偶数行用红球）

对于每种情况，我们从第1行开始逐行构建三角形：

  • 第i行需要i个球
  • 检查当前颜色是否有足够的球
  • 如果没有足够的球，则无法继续构建更高的三角形

算法步骤：

  1. 定义一个辅助函数计算在给定起始颜色下能达到的最大高度
  2. 分别计算红球开始和蓝球开始两种情况的最大高度
  3. 返回两种情况中的较大值

这种贪心策略是正确的，因为我们总是优先构建较低的行，这样能最大化利用现有的球数。

时间复杂度很低，因为在最坏情况下，三角形高度不会超过约14层（1+2+…+14=105 > 100）。

代码实现

class Solution {
public:
    int maxHeightOfTriangle(int red, int blue) {
        return max(getMaxHeight(red, blue), getMaxHeight(blue, red));
    }
    
private:
    int getMaxHeight(int first, int second) {
        int height = 0;
        int level = 1;
        
        while (true) {
            if (level % 2 == 1) {
                // 奇数行使用第一种颜色
                if (first >= level) {
                    first -= level;
                    height++;
                } else {
                    break;
                }
            } else {
                // 偶数行使用第二种颜色
                if (second >= level) {
                    second -= level;
                    height++;
                } else {
                    break;
                }
            }
            level++;
        }
        
        return height;
    }
};

class Solution:
    def maxHeightOfTriangle(self, red: int, blue: int) -> int:
        def get_max_height(first: int, second: int) -> int:
            height = 0
            level = 1
            
            while True:
                if level % 2 == 1:
                    # 奇数行使用第一种颜色
                    if first >= level:
                        first -= level
                        height += 1
                    else:
                        break
                else:
                    # 偶数行使用第二种颜色
                    if second >= level:
                        second -= level
                        height += 1
                    else:
                        break
                level += 1
            
            return height
        
        return max(get_max_height(red, blue), get_max_height(blue, red))

public class Solution {
    public int MaxHeightOfTriangle(int red, int blue) {
        return Math.Max(GetMaxHeight(red, blue), GetMaxHeight(blue, red));
    }
    
    private int GetMaxHeight(int first, int second) {
        int height = 0;
        int level = 1;
        
        while (true) {
            if (level % 2 == 1) {
                // 奇数行使用第一种颜色
                if (first >= level) {
                    first -= level;
                    height++;
                } else {
                    break;
                }
            } else {
                // 偶数行使用第二种颜色
                if (second >= level) {
                    second -= level;
                    height++;
                } else {
                    break;
                }
            }
            level++;
        }
        
        return height;
    }
}

var maxHeightOfTriangle = function(red, blue) {
    function getHeight(first, second) {
        let height = 0;
        let row = 1;
        let useFirst = true;
        
        while (true) {
            if (useFirst) {
                if (first >= row) {
                    first -= row;
                } else {
                    break;
                }
            } else {
                if (second >= row) {
                    second -= row;
                } else {
                    break;
                }
            }
            height++;
            row++;
            useFirst = !useFirst;
        }
        
        return height;
    }
    
    return Math.max(getHeight(red, blue), getHeight(blue, red));
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(√n)其中 n 为球的总数，三角形的最大高度约为 √(2n)
空间复杂度O(1)只使用常数额外空间