leetcode 441. 排列硬币

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

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

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

示例 1:
n = 5
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤
因为第三行不完整，所以返回2.

示例 2:
n = 8
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
因为第四行不完整，所以返回3.

有2种解法：
这道题要用硬币去一层层堆楼梯。其实很容易想到累加和。

题目的意思其实就是从1~x层完整楼梯硬币数量加起来，要小于等于n，求最大的x。说到加起来的数量，很容易想到求累加和，我们知道求累加和的公式为：

sum = (1+x)*x/2

这里就是要求 sum <= n 了。我们反过来求层数x。如果直接开方来求会存在错误，必须因式分解求得准确的x值：

(1+x)x/2 <= n
x + xx <= 2n
4xx + 4x <= 8n
(2x + 1)(2x + 1) - 1 <= 8n
x <= (sqrt(8n + 1) - 1) / 2

其中Math.sqrt()是求平方根的函数。这样我们就求出了x

 var arrangeCoins = function(n) {
    //O(1)
 return Math.floor((Math.sqrt(8*n + 1) - 1)/2);
};

 var arrangeCoins = function(n) {
    //O(n)
    var i = 1;
    while(n >= i){
        n = n - i;
        i++;
    }
    return i-1;
};