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:
n = 5
The coins can form the following rows:
¤
¤ ¤
¤ ¤
Because the 3rd row is incomplete, we return 2.
Example 2:
n = 8
The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
Because the 4th row is incomplete, we return 3.
这道题给了我们n个硬币，让我们按一定规律排列，第一行放1个，第二行放2个，以此类推，问我们有多少行能放满。通过分析题目中的例子可以得知最后一行只有两种情况，放满和没放满。由于是按等差数列排放的，我们可以快速计算出前i行的硬币总数。我们先来看一种O(n)的方法，非常简单粗暴，就是从第一行开始，一行一行的从n中减去，如果此时剩余的硬币没法满足下一行需要的硬币数了，我们之间返回当前行数即可，参见代码如下：
解法一：
class Solution {
public:
int arrangeCoins(int n) {
int cur = 1, rem = n - 1;
while (rem >= cur + 1) {
++cur;
rem -= cur;
}
return n == 0 ? 0 : cur;
}
};
再来看一种O(lgn)的方法，用到了二分搜索法，我们搜索前i行之和刚好大于n的临界点，这样我们减一个就是能排满的行数，注意我们计算前i行之和有可能会整型溢出，所以我们需要将变量都定义成长整型，参见代码如下：
解法二：
class Solution {
public:
int arrangeCoins(int n) {
if (n <= 1) return n;
long low = 1, high = n;
while (low < high) {
long mid = low + (high - low) / 2;
if (mid * (mid + 1) / 2 <= n) low = mid + 1;
else high = mid;
}
return low - 1;
}
};
再来看一种数学解法O(1)，充分利用了等差数列的性质，我们建立等式, n = (1 + x) * x / 2, 我们用一元二次方程的求根公式可以得到 x = (-1 + sqrt(8 * n + 1)) / 2, 然后取整后就是能填满的行数，一行搞定简直丧心病狂啊：
解法三：
class Solution {
public:
int arrangeCoins(int n) {
return (int)((-1 + sqrt(1 + 8 * (long)n)) / 2);
}
};
参考资料：
https://discuss.leetcode.com/topic/65664/my-55ms-c-solution
https://discuss.leetcode.com/topic/65575/java-o-1-solution-math-problem
https://discuss.leetcode.com/topic/65631/c-three-solutions-o-n-o-logn-o-1/2
LeetCode All in One 题目讲解汇总(持续更新中…)
转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com
