题目描述

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

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

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

示例

• 示例一

n = 5

硬币可排列成以下几行:
¤
¤ ¤
¤ ¤

因为第三行不完整，所以返回2.

• 示例二

n = 8

硬币可排列成以下几行:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

因为第四行不完整，所以返回3.

解答

• 自己答案

class Solution {
    public int arrangeCoins(int n) {
        int sum = n;
        int j = 0;
        for(int i=1;i<=n;i++){
            if(sum-i<0){
                break;
            }
            sum-=i;
            j++;
        }
        return j;
    }
}

• 其它答案

class Solution{
    public int arrangeCoins(int n){
        return (int)((-1+Math.sqrt(1+8*(long)n))/2);
    }
}

设一共有k行，计算等差数列求和：
S = na1+ n(n-1)d/2
得 k+k(k-1)/2 = n