Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 0de04e4

Browse filesBrowse files
yanglbmeyanglbme
authored
feat: add weekly contest 403 (doocs#3178)
1 parent 7ec1ece commit 0de04e4
Copy full SHA for 0de04e4

File tree

Expand file treeCollapse file tree

22 files changed

+1080
-1
lines changed
Open diff view settings
Filter options
Expand file treeCollapse file tree

22 files changed

+1080
-1
lines changed
Open diff view settings
Collapse file

‎solution/3200-3299/3200.Maximum Height of a Triangle/README.md‎

Copy file name to clipboard
+184Lines changed: 184 additions & 0 deletions
  • Display the source diff
  • Display the rich diff
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,184 @@
1+
---
2+
comments: true
3+
difficulty: 简单
4+
edit_url: https://github.com/doocs/leetcode/edit/main/solution/3200-3299/3200.Maximum%20Height%20of%20a%20Triangle/README.md
5+
---
6+
7+
<!-- problem:start -->
8+
9+
# [3200. 三角形的最大高度](https://leetcode.cn/problems/maximum-height-of-a-triangle)
10+
11+
[English Version](/solution/3200-3299/3200.Maximum%20Height%20of%20a%20Triangle/README_EN.md)
12+
13+
## 题目描述
14+
15+
<!-- description:start -->
16+
17+
<p>给你两个整数 <code>red</code> 和 <code>blue</code>，分别表示红色球和蓝色球的数量。你需要使用这些球来组成一个三角形，满足第 1 行有 1 个球，第 2 行有 2 个球，第 3 行有 3 个球，依此类推。</p>
18+
19+
<p>每一行的球必须是 <strong>相同 </strong>颜色，且相邻行的颜色必须<strong> 不同</strong>。</p>
20+
21+
<p>返回可以实现的三角形的 <strong>最大 </strong>高度。</p>
22+
23+
<p>&nbsp;</p>
24+
25+
<p><strong class="example">示例 1：</strong></p>
26+
27+
<div class="example-block">
28+
<p><strong>输入：</strong> <span class="example-io">red = 2, blue = 4</span></p>
29+
30+
<p><strong>输出：</strong> 3</p>
31+
32+
<p><strong>解释：</strong></p>
33+
34+
<p><img alt="" src="https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/3200-3299/3200.Maximum%20Height%20of%20a%20Triangle/images/brb.png" style="width: 300px; height: 240px; padding: 10px;" /></p>
35+
36+
<p>上图显示了唯一可能的排列方式。</p>
37+
</div>
38+
39+
<p><strong class="example">示例 2：</strong></p>
40+
41+
<div class="example-block">
42+
<p><strong>输入：</strong> <span class="example-io">red = 2, blue = 1</span></p>
43+
44+
<p><strong>输出：</strong> <span class="example-io">2</span></p>
45+
46+
<p><strong>解释：</strong></p>
47+
48+
<p><img alt="" src="https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/3200-3299/3200.Maximum%20Height%20of%20a%20Triangle/images/br.png" style="width: 150px; height: 135px; padding: 10px;" /><br />
49+
上图显示了唯一可能的排列方式。</p>
50+
</div>
51+
52+
<p><strong class="example">示例 3：</strong></p>
53+
54+
<div class="example-block">
55+
<p><strong>输入：</strong> <span class="example-io">red = 1, blue = 1</span></p>
56+
57+
<p><strong>输出：</strong> <span class="example-io">1</span></p>
58+
</div>
59+
60+
<p><strong class="example">示例 4：</strong></p>
61+
62+
<div class="example-block">
63+
<p><strong>输入：</strong> <span class="example-io">red = 10, blue = 1</span></p>
64+
65+
<p><strong>输出：</strong> <span class="example-io">2</span></p>
66+
67+
<p><strong>解释：</strong></p>
68+
69+
<p><img alt="" src="https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/3200-3299/3200.Maximum%20Height%20of%20a%20Triangle/images/br.png" style="width: 150px; height: 135px; padding: 10px;" /><br />
70+
上图显示了唯一可能的排列方式。</p>
71+
</div>
72+
73+
<p>&nbsp;</p>
74+
75+
<p><strong>提示：</strong></p>
76+
77+
<ul>
78+
<li><code>1 &lt;= red, blue &lt;= 100</code></li>
79+
</ul>
80+
81+
<!-- description:end -->
82+
83+
## 解法
84+
85+
<!-- solution:start -->
86+
87+
### 方法一：模拟
88+
89+
我们可以枚举第一行的颜色，然后模拟构造三角形，计算最大高度。
90+
91+
时间复杂度 $O(\sqrt{n})$，其中 $n$ 为红色球和蓝色球的数量。空间复杂度 $O(1)$。
92+
93+
<!-- tabs:start -->
94+
95+
#### Python3
96+
97+
```python
98+
class Solution:
99+
def maxHeightOfTriangle(self, red: int, blue: int) -> int:
100+
ans = 0
101+
for k in range(2):
102+
c = [red, blue]
103+
i, j = 1, k
104+
while i <= c[j]:
105+
c[j] -= i
106+
j ^= 1
107+
ans = max(ans, i)
108+
i += 1
109+
return ans
110+
```
111+
112+
#### Java
113+
114+
```java
115+
class Solution {
116+
public int maxHeightOfTriangle(int red, int blue) {
117+
int ans = 0;
118+
for (int k = 0; k < 2; ++k) {
119+
int[] c = {red, blue};
120+
for (int i = 1, j = k; i <= c[j]; j ^= 1, ++i) {
121+
c[j] -= i;
122+
ans = Math.max(ans, i);
123+
}
124+
}
125+
return ans;
126+
}
127+
}
128+
```
129+
130+
#### C++
131+
132+
```cpp
133+
class Solution {
134+
public:
135+
int maxHeightOfTriangle(int red, int blue) {
136+
int ans = 0;
137+
for (int k = 0; k < 2; ++k) {
138+
int c[2] = {red, blue};
139+
for (int i = 1, j = k; i <= c[j]; j ^= 1, ++i) {
140+
c[j] -= i;
141+
ans = max(ans, i);
142+
}
143+
}
144+
return ans;
145+
}
146+
};
147+
```
148+
149+
#### Go
150+
151+
```go
152+
func maxHeightOfTriangle(red int, blue int) (ans int) {
153+
for k := 0; k < 2; k++ {
154+
c := [2]int{red, blue}
155+
for i, j := 1, k; i <= c[j]; i, j = i+1, j^1 {
156+
c[j] -= i
157+
ans = max(ans, i)
158+
}
159+
}
160+
return
161+
}
162+
```
163+
164+
#### TypeScript
165+
166+
```ts
167+
function maxHeightOfTriangle(red: number, blue: number): number {
168+
let ans = 0;
169+
for (let k = 0; k < 2; ++k) {
170+
const c: [number, number] = [red, blue];
171+
for (let i = 1, j = k; i <= c[j]; ++i, j ^= 1) {
172+
c[j] -= i;
173+
ans = Math.max(ans, i);
174+
}
175+
}
176+
return ans;
177+
}
178+
```
179+
180+
<!-- tabs:end -->
181+
182+
<!-- solution:end -->
183+
184+
<!-- problem:end -->
Collapse file

‎solution/3200-3299/3200.Maximum Height of a Triangle/README_EN.md‎

Copy file name to clipboard
+182Lines changed: 182 additions & 0 deletions
  • Display the source diff
  • Display the rich diff
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,182 @@
1+
---
2+
comments: true
3+
difficulty: Easy
4+
edit_url: https://github.com/doocs/leetcode/edit/main/solution/3200-3299/3200.Maximum%20Height%20of%20a%20Triangle/README_EN.md
5+
---
6+
7+
<!-- problem:start -->
8+
9+
# [3200. Maximum Height of a Triangle](https://leetcode.com/problems/maximum-height-of-a-triangle)
10+
11+
[中文文档](/solution/3200-3299/3200.Maximum%20Height%20of%20a%20Triangle/README.md)
12+
13+
## Description
14+
15+
<!-- description:start -->
16+
17+
<p>You are given two integers <code>red</code> and <code>blue</code> representing the count of red and blue colored balls. You have to arrange these balls to form a triangle such that the 1<sup>st</sup> row will have 1 ball, the 2<sup>nd</sup> row will have 2 balls, the 3<sup>rd</sup> row will have 3 balls, and so on.</p>
18+
19+
<p>All the balls in a particular row should be the <strong>same</strong> color, and adjacent rows should have <strong>different</strong> colors.</p>
20+
21+
<p>Return the <strong>maximum</strong><em> height of the triangle</em> that can be achieved.</p>
22+
23+
<p>&nbsp;</p>
24+
<p><strong class="example">Example 1:</strong></p>
25+
26+
<div class="example-block">
27+
<p><strong>Input:</strong> <span class="example-io">red = 2, blue = 4</span></p>
28+
29+
<p><strong>Output:</strong> 3</p>
30+
31+
<p><strong>Explanation:</strong></p>
32+
33+
<p><img alt="" src="https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/3200-3299/3200.Maximum%20Height%20of%20a%20Triangle/images/brb.png" style="width: 300px; height: 240px; padding: 10px;" /></p>
34+
35+
<p>The only possible arrangement is shown above.</p>
36+
</div>
37+
38+
<p><strong class="example">Example 2:</strong></p>
39+
40+
<div class="example-block">
41+
<p><strong>Input:</strong> <span class="example-io">red = 2, blue = 1</span></p>
42+
43+
<p><strong>Output:</strong> <span class="example-io">2</span></p>
44+
45+
<p><strong>Explanation:</strong></p>
46+
47+
<p><img alt="" src="https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/3200-3299/3200.Maximum%20Height%20of%20a%20Triangle/images/br.png" style="width: 150px; height: 135px; padding: 10px;" /><br />
48+
The only possible arrangement is shown above.</p>
49+
</div>
50+
51+
<p><strong class="example">Example 3:</strong></p>
52+
53+
<div class="example-block">
54+
<p><strong>Input:</strong> <span class="example-io">red = 1, blue = 1</span></p>
55+
56+
<p><strong>Output:</strong> <span class="example-io">1</span></p>
57+
</div>
58+
59+
<p><strong class="example">Example 4:</strong></p>
60+
61+
<div class="example-block">
62+
<p><strong>Input:</strong> <span class="example-io">red = 10, blue = 1</span></p>
63+
64+
<p><strong>Output:</strong> <span class="example-io">2</span></p>
65+
66+
<p><strong>Explanation:</strong></p>
67+
68+
<p><img alt="" src="https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/3200-3299/3200.Maximum%20Height%20of%20a%20Triangle/images/br.png" style="width: 150px; height: 135px; padding: 10px;" /><br />
69+
The only possible arrangement is shown above.</p>
70+
</div>
71+
72+
<p>&nbsp;</p>
73+
<p><strong>Constraints:</strong></p>
74+
75+
<ul>
76+
<li><code>1 &lt;= red, blue &lt;= 100</code></li>
77+
</ul>
78+
79+
<!-- description:end -->
80+
81+
## Solutions
82+
83+
<!-- solution:start -->
84+
85+
### Solution 1: Simulation
86+
87+
We can enumerate the color of the first row, then simulate the construction of the triangle, calculating the maximum height.
88+
89+
The time complexity is $O(\sqrt{n})$, where $n$ is the number of red and blue balls. The space complexity is $O(1)$.
90+
91+
<!-- tabs:start -->
92+
93+
#### Python3
94+
95+
```python
96+
class Solution:
97+
def maxHeightOfTriangle(self, red: int, blue: int) -> int:
98+
ans = 0
99+
for k in range(2):
100+
c = [red, blue]
101+
i, j = 1, k
102+
while i <= c[j]:
103+
c[j] -= i
104+
j ^= 1
105+
ans = max(ans, i)
106+
i += 1
107+
return ans
108+
```
109+
110+
#### Java
111+
112+
```java
113+
class Solution {
114+
public int maxHeightOfTriangle(int red, int blue) {
115+
int ans = 0;
116+
for (int k = 0; k < 2; ++k) {
117+
int[] c = {red, blue};
118+
for (int i = 1, j = k; i <= c[j]; j ^= 1, ++i) {
119+
c[j] -= i;
120+
ans = Math.max(ans, i);
121+
}
122+
}
123+
return ans;
124+
}
125+
}
126+
```
127+
128+
#### C++
129+
130+
```cpp
131+
class Solution {
132+
public:
133+
int maxHeightOfTriangle(int red, int blue) {
134+
int ans = 0;
135+
for (int k = 0; k < 2; ++k) {
136+
int c[2] = {red, blue};
137+
for (int i = 1, j = k; i <= c[j]; j ^= 1, ++i) {
138+
c[j] -= i;
139+
ans = max(ans, i);
140+
}
141+
}
142+
return ans;
143+
}
144+
};
145+
```
146+
147+
#### Go
148+
149+
```go
150+
func maxHeightOfTriangle(red int, blue int) (ans int) {
151+
for k := 0; k < 2; k++ {
152+
c := [2]int{red, blue}
153+
for i, j := 1, k; i <= c[j]; i, j = i+1, j^1 {
154+
c[j] -= i
155+
ans = max(ans, i)
156+
}
157+
}
158+
return
159+
}
160+
```
161+
162+
#### TypeScript
163+
164+
```ts
165+
function maxHeightOfTriangle(red: number, blue: number): number {
166+
let ans = 0;
167+
for (let k = 0; k < 2; ++k) {
168+
const c: [number, number] = [red, blue];
169+
for (let i = 1, j = k; i <= c[j]; ++i, j ^= 1) {
170+
c[j] -= i;
171+
ans = Math.max(ans, i);
172+
}
173+
}
174+
return ans;
175+
}
176+
```
177+
178+
<!-- tabs:end -->
179+
180+
<!-- solution:end -->
181+
182+
<!-- problem:end -->
Collapse file

‎solution/3200-3299/3200.Maximum Height of a Triangle/Solution.cpp‎

Copy file name to clipboard
+14Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
class Solution {
2+
public:
3+
int maxHeightOfTriangle(int red, int blue) {
4+
int ans = 0;
5+
for (int k = 0; k < 2; ++k) {
6+
int c[2] = {red, blue};
7+
for (int i = 1, j = k; i <= c[j]; j ^= 1, ++i) {
8+
c[j] -= i;
9+
ans = max(ans, i);
10+
}
11+
}
12+
return ans;
13+
}
14+
};
Collapse file

‎solution/3200-3299/3200.Maximum Height of a Triangle/Solution.go‎

Copy file name to clipboard
+10Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
func maxHeightOfTriangle(red int, blue int) (ans int) {
2+
for k := 0; k < 2; k++ {
3+
c := [2]int{red, blue}
4+
for i, j := 1, k; i <= c[j]; i, j = i+1, j^1 {
5+
c[j] -= i
6+
ans = max(ans, i)
7+
}
8+
}
9+
return
10+
}

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.