Intuition#

找最大的 k 使得 k*(k+1)/2 <= n，可以用二分搜尋或數學公式。

• 前 k 行需要 k * (k + 1) / 2 枚硬幣
• 問題轉化為：找最大的 k 使得 k * (k + 1) / 2 <= n

Approaches#

1: 模擬法#

• 概念: 逐行扣除硬幣直到不夠為止
• 時間複雜度: O(sqrt(n))
• 空間複雜度: O(1)

class Solution {
    fun arrangeCoins(n: Int): Int {
        var remaining = n
        var row = 0
        while (remaining > row) {
            row++
            remaining -= row
        }
        return row
    }
}

⭐2: Binary Search#

• 概念: 在 [1, n] 上二分搜尋最大的 k 使得 k*(k+1)/2 <= n
• 時間複雜度: O(log n)
• 空間複雜度: 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()
    }
}

注意使用 Long 避免 mid * (mid + 1) 溢位。這是找最大可行值，所以用 left = mid 配合 mid = left + (right - left + 1) / 2 避免無限迴圈。

3: 數學公式#

• 概念: 解二次方程式 k*(k+1)/2 = n，得 k = (-1 + sqrt(1 + 8n)) / 2
• 時間複雜度: O(1)
• 空間複雜度: O(1)

class Solution {
    fun arrangeCoins(n: Int): Int {
        return ((-1.0 + Math.sqrt(1.0 + 8.0 * n)) / 2.0).toInt()
    }
}

🔑 Takeaways#

• Pattern: 在答案空間上二分搜尋最大可行值
• 關鍵技巧: 找最大可行值時的二分模板與找最小可行值不同：使用 left = mid、right = mid - 1，並且 mid 要向上取整（+1）避免死迴圈