What is the pattern used in the Maximum Height of a Triangle problem?

The problem follows an array plus enumeration pattern, where different configurations of alternating row colors need to be evaluated to maximize the triangle's height.

What is the maximum height of the triangle if the red balls are much fewer than the blue balls?

In this case, the maximum height will depend on the number of rows that can be filled using the available red balls, while adhering to the alternating color constraint.

How does the alternating color requirement affect the triangle's height?

The alternating color requirement means that the sequence of rows must alternate between red and blue balls. This constraint limits the number of rows that can be formed with the given red and blue balls.

Can I use any color combination for the rows in the Maximum Height of a Triangle problem?

No, you must alternate the color of adjacent rows, which restricts your choices to two configurations: red on top or blue on top.

What is the expected time complexity of solving the Maximum Height of a Triangle problem?

The time complexity depends on the approach you use to simulate the ball arrangement, but a greedy enumeration approach typically has a time complexity of O(N), where N is the number of rows that can be formed.

#3200

Easy

auto_awesome数组·结合·enumeration

LeetCode 题解工作台

三角形的最大高度

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

数组枚举

题目描述

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

lightbulb

解题思路

方法一：模拟

我们可以枚举第一行的颜色，然后模拟构造三角形，计算最大高度。

时间复杂度 $O(\sqrt{n})$ ，其中 $n$ 为红色球和蓝色球的数量。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def maxHeightOfTriangle(self, red: int, blue: int) -> int:
        ans = 0
        for k in range(2):
            c = [red, blue]
            i, j = 1, k
            while i <= c[j]:
                c[j] -= i
                j ^= 1
                ans = max(ans, i)
                i += 1
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate demonstrates understanding of array plus enumeration.
question_mark
Candidate should be able to correctly switch between color configurations.
question_mark
Check if candidate understands the importance of maximizing row formation without violating color constraints.

warning

常见陷阱

外企场景

error
Misunderstanding the row constraints, especially with alternating colors.
error
Failing to account for both color possibilities (red or blue on top).
error
Incorrectly calculating the number of rows that can be formed given the available red and blue balls.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the number of balls is drastically different between red and blue?
arrow_right_alt
How would the problem change if the number of rows allowed was capped?
arrow_right_alt
What if additional color constraints were introduced, such as using multiple colors?

help

常见问题

外企场景

继续练习

#3197 包含所有 1 的最小矩形面积 II #3256 放三个车的价值之和最大 I #3257 放三个车的价值之和最大 II