各位题友大家好，@负雪明烛 又出现了。

题意

第 i 层可以放置 i 个硬币，将 n 个硬币按行排列，计算并返回可形成 完整阶梯行 的总行数。

解题思路

解法一：模拟法

一看题目是 Easy，用暴力的模拟法应该能通过。

定义了两个变量：

  • level 表示遍历到了第 level 层，同时这层可以放 level 个硬币。
  • count 表示累加了 level 层之后，总的有多少硬币。

因为最后一行可能不满，所以当 count + level + 1 <= n的时候，才累加上这一层的硬币数。其中 level + 1表示下一层的硬币数目。

注意：count + level + 1有可能会超过 int 最大值，所以把 count 定义为了 long 型。

代码如下：

  1. class Solution {
  2. public:
  3.     int arrangeCoins(int n) {
  4.         long level = 0; // 当前层
  5.         long count = 0; // 加上 level 层之后，总的有多少硬币
  6.         while (count + level + 1 <= n) { // level + 1 表示下一层的数目
  7.             level ++; // 得到下一层的数目
  8.             count += level; // 累加下一层的数目
  9.         }
  10.         return level;
  11.     }
  12. };
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$

解法二：二分查找

每层可以容纳的硬币数量分别是 1, 2, 3, 4, ..., i，根据等差数列的计算公式，可以求得当第 i 行铺满的时候，第 0 ~ i 行总的硬币数目有 (i + 1) * i / 2。

那么可以使用二分查找，快速的查找出 (i + 1) * i / 2 <= n 的最大数字 $i$ ，即为所求。

二分查找的模板可以见 AlgoWiki：https://ojeveryday.github.io/AlgoWiki/#/BinarySearch/README

下面的代码中，二分查找定义的区间是 [left, right]双闭区间。只要符合条件 (mid + 1) * mid / 2 <= n ，就让 left = mid + 1，所以会导致 left 多计算一行，因此，最终 left 需要减一。

注意：mid * (mid + 1) / 2有可能会非常大，所以我把 mid 的类型设置为了 long long.

class Solution {
public:
    int arrangeCoins(int n) {
        int left = 0;
        int right = n; // [left, right]
        while (left <= right) {
            long long mid = left + (right - left) / 2;
            if (mid * (mid + 1) / 2 <= n) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left - 1;
    }
};
  • 时间复杂度：$O(log(n))$
  • 空间复杂度：$O(1)$

方法三：数学公式

根据二分查找部分的分析，我们其实就是求满足 (i + 1) * i / 2 = n 这个方程，通过求解一元二次方程就能得到 i = (-1 + sqrt(8 * n + 1)) / 2，此时 i 是个浮点数，向下取整就得到了完整阶梯行。

class Solution {
public:
    int arrangeCoins(int n) {
        return (int)((-1 + sqrt(1 + 8 * (long) n)) / 2);
    }
};
  • 时间复杂度：$O(1)$

  • 空间复杂度：$O(1)$

    刷题心得

  • 模拟法最需要注意的是每个变量的准确含义：比如 count 是累加了 level 后，还是累加了 level 前？

  • 二分查找的难点在于把本题抽象成为一个查找问题：需要数学公式的抽象。
  • 数学公式的难点是：公式求解，以及变量类型。

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家 AC 多多，Offer 多多！我们下期再见！