1.题目

你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。

给定一个数字 n，找出可形成完整阶梯行的总行数。

n 是一个非负整数，并且在32位有符号整型的范围内。

示例：

  1. n = 5
  2. 硬币可排列成以下几行:
  3. ¤
  4. ¤ ¤
  5. ¤ ¤
  6. 因为第三行不完整，所以返回2.
  9. n = 8
  10. 硬币可排列成以下几行:
  11. ¤
  12. ¤ ¤
  13. ¤ ¤ ¤
  14. ¤ ¤
  15. 因为第四行不完整，所以返回3.

2.思路

等差数列求和公式

441. 排列硬币 - 图1%7D%7B2%7Dd%2Cn%5Cin%20N%5E*#card=math&code=S_n%3Dna_1%2B%5Cfrac%7Bn%28n-1%29%7D%7B2%7Dd%2Cn%5Cin%20N%5E%2A)

从第1行阶梯开始累加硬币，即1 + 2 + 3 + … + k <= n。k从1开始枚举，由等差数列求和公式可得441. 排列硬币 - 图2%20%C3%97%20%5Cfrac%7Bk%7D%7B2%7D#card=math&code=sum%20%3D%20%281%20%2B%20k%29%20%C3%97%20%5Cfrac%7Bk%7D%7B2%7D)，最后while循环结束是因为sum > n，所以要返回k - 1。

  1.     public int arrangeCoins(int n) {
  2.         long k = 1, sum = 1;
  3.         while (sum <= n) {
  4.             k++;
  5.             sum = (1 + k) * k / 2;
  6.         }
  7.         return (int) k - 1;
  8.     }

还有一种二分查找的：

答案的范围是[0,n]的有序区间，所以可以使用二分查找。我们要在[0,n]中找到一个数k(代码中的mid)，使得441. 排列硬币 - 图3%20%C3%97%20%5Cfrac%7Bk%7D%7B2%7D#card=math&code=%281%20%2B%20k%29%20%C3%97%20%5Cfrac%7Bk%7D%7B2%7D)刚好小于等于n，如果大于n，就排除一半区间。

  1.     public int arrangeCoins(int n) {
  2.         long left = 0, right = n;
  3.         while (left < right) {
  4.             long mid = left + (right - left + 1) / 2;
  5.             long sum = (1 + mid) * mid / 2;
  6.             // sum大于n一定不是解
  7.             if (sum > n) {
  8.                 // 下一轮搜索区间是 [left, mid - 1]
  9.                 right = mid - 1;
  10.             } else {
  11.                 // 下一轮搜索区间是 [mid, right]
  12.                 left = mid;
  13.             }
  14.         }
  15.         return (int) left;
  16.     }

作者：maczhen
链接：https://leetcode-cn.com/problems/arranging-coins/solution/441-pai-lie-ying-bi-javabao-li-er-fen-ch-sqnv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。