【从零开始的LeetCode-算法】3200. 三角形的最大高度

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

我的解答：

class Solution {
    public int maxHeightOfTriangle(int red, int blue) {
        int max_box = red >= blue ? red : blue; 
        int min_box = red >= blue ? blue : red; 
        // 作为奇数层，每多一层奇数层，总数应为 1 4 9 16  ... 规律为n^2 
        // 作为偶数层，每多一层哦数层，总数应为 2 6 12 20...规律为n(n + 1)
        
        // 尝试使用球数最少的颜色做计算,算出奇数层最高层数
        int min_odd_level  = (int)Math.floor(Math.sqrt(min_box));
        // 判断球数最多的颜色球数量是否要大于等于奇数层*（奇数层 + 1）。
        // 如果满足，则说明在最后的奇数层下方，还可加一层偶数层，此时偶数层比奇数层相同
        int max_even_level = max_box >= min_odd_level * (min_odd_level + 1) ? min_odd_level : min_odd_level - 1;
        
        // 判断作为偶数层时层数能否增加
        int min_even_level = min_box >= min_odd_level * (min_odd_level + 1) ? min_odd_level : 0;
        // 同理：判断球数最多的颜色球数量是否要大于等于(偶数层+1)^2。
        // 如果满足，则说明在最后的偶数层下方，还可加一层奇数层，此时偶数层比奇数层多一层
        int max_odd_level  = max_box >= (min_even_level + 1) * (min_even_level + 1) ? min_even_level + 1 : min_even_level;


        return  Math.max(min_odd_level + max_even_level,min_even_level + max_odd_level);
    }
}

优化：

 移除使用sqrt()求根函数，避免内置函数使用的方法复杂且耗时【其实影响并不大，上述方法重复提交也有概率达到第一矩形上，跟网络有关】

class Solution {
    public int maxHeightOfTriangle(int red, int blue) {
        int max_box = Math.max(red,blue);
        int min_box = Math.min(red,blue);
        // 作为奇数层，每多一层奇数层，总数应为 1 4 9 16 ... 规律为n^2
        // 作为偶数层，每多一层哦数层，总数应为 2 6 12 20...规律为n(n + 1)
        for (int i = 1;; i++) {
            // 如果不满足当前层的奇数层所需数量
            if(min_box < i * i) {
                // 判断是否满足上一层偶数层数量
                // 满足，说明球数最少的颜色小球放置在偶数行能使三角形高度最高
                // 反之，说明球数最少的颜色小球放置在奇数行能使三角形高度最高
                if (min_box >= (i - 1) * i) {
                    // 判断球数最多的颜色小球是否满足当前行所需奇数球数
                    return max_box >= i*i ? 2 * i - 1 : 2 * (i - 1);
                }else{
                    // 判断球数最多的颜色小球是否满足上一行所需偶数球数
                    return max_box >= i*(i - 1) ? 2 * (i - 1) : 2 * (i - 1) - 1;
                }
            }
            // 设为奇数层时，刚好全部放置完，此时是最优的结果
            if(min_box == i * i){
                // 判断球数最多的颜色小球是否满足当前行所需偶数球数
                return max_box >= i * (i + 1) ? 2*i : 2*i - 1;
            }
        }

    }
}

原文地址：https://blog.csdn.net/qq_40878316/article/details/142945811

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！