你有
n枚硬幣，想排成階梯形。第k行必須恰好有k枚硬幣。回傳可以完整填滿的行數。
Example:
Input: n = 8 Output: 3（第 1 行 1 枚 + 第 2 行 2 枚 + 第 3 行 3 枚 = 6，剩 2 枚不夠填第 4 行）
Intuition
TIP
找最大的 k 使得 k*(k+1)/2 <= n，可以用二分搜尋或數學公式。
- 前 k 行需要
k * (k + 1) / 2枚硬幣 - 問題轉化為：找最大的 k 使得
k * (k + 1) / 2 <= n
Approaches
1. Simulation — O(sqrt(n)) / O(1)
- Idea: 逐行扣除硬幣直到不夠為止
- Time:
O(sqrt(n)) - Space:
O(1)
Simulation Code
class Solution {
fun arrangeCoins(n: Int): Int {
var remaining = n
var row = 0
while (remaining > row) {
row++
remaining -= row
}
return row
}
}⭐ 2. Binary Search — O(log n) / O(1)
- Idea: 在 [1, n] 上二分搜尋最大的 k 使得
k*(k+1)/2 <= n - Time:
O(log n) - Space:
O(1)
class Solution {
fun arrangeCoins(n: Int): Int {
var left = 1L
var right = n.toLong()
while (left < right) {
val mid = left + (right - left + 1) / 2
if (mid * (mid + 1) / 2 <= n) {
left = mid
} else {
right = mid - 1
}
}
return left.toInt()
}
}WARNING
注意使用 Long 避免 mid * (mid + 1) 溢位。這是找最大可行值，所以用 left = mid 配合 mid = left + (right - left + 1) / 2 避免無限迴圈。
3. Math Formula — O(1) / O(1)
- Idea: 解二次方程式
k*(k+1)/2 = n，得k = (-1 + sqrt(1 + 8n)) / 2 - Time:
O(1) - Space:
O(1)
Math Formula Code
class Solution {
fun arrangeCoins(n: Int): Int {
return ((-1.0 + Math.sqrt(1.0 + 8.0 * n)) / 2.0).toInt()
}
}🔑 Takeaways
- Pattern: 在答案空間上二分搜尋最大可行值
- Key trick: 找最大可行值時的二分模板與找最小可行值不同：使用
left = mid、right = mid - 1，並且mid要向上取整（+1）避免死迴圈