题目

You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.

Given n, find the total number of full staircase rows that can be formed.

n is a non-negative integer and fits within the range of a 32-bit signed integer.

Example 1:

  1. n = 5
  3. The coins can form the following rows:
  4. ¤
  5. ¤ ¤
  6. ¤ ¤
  8. Because the 3rd row is incomplete, we return 2.

Example 2:

  1. n = 8
  3. The coins can form the following rows:
  4. ¤
  5. ¤ ¤
  6. ¤ ¤ ¤
  7. ¤ ¤
  9. Because the 4th row is incomplete, we return 3.

题意

将n个硬币叠成阶梯状，求能达到的最大阶梯数。

思路

可以直接累减，或者二分查找，或者直接公式解答 (从 0441. Arranging Coins (E) - 图1 推导)。

代码实现

Java

累减

  1. class Solution {
  2.     public int arrangeCoins(int n) {
  3.         int i = 1;
  4.         while (n >= i) {
  5.             n -= i++;
  6.         }
  7.         return i - 1;
  8.     }
  9. }

二分

  1. class Solution {
  2.     public int arrangeCoins(int n) {
  3.         long left = 0, right = n;
  4.         while (left <= right) {
  5.             long mid = (right - left) / 2 + left;
  6.             long sum = (mid + 1) * mid / 2;
  7.             if (sum < n) {
  8.                 left = mid + 1;
  9.             } else if (sum > n) {
  10.                 right = mid - 1;
  11.             } else {
  12.                 return (int) mid;
  13.             }
  14.         }
  15.         return (int) right;
  16.     }
  17. }

公式计算

  1. class Solution {
  2.     public int arrangeCoins(int n) {
  3.         return (int) (Math.sqrt(2 * (long) n + 0.25) - 0.5);
  4.     }
  5. }