排列硬币

解题思路：

  1. 根据等差数列求和公式可知，前 k 个完整阶梯行所需的硬币数量为 total = k*(k+1)/2；

  2. 可以通过二分查找计算 n 枚硬币可形成的完整阶梯行的总行数；

复杂度：

  1. 时间复杂度：O(logn)；

  2. 空间复杂度：O(1)；

代码实现：（左闭右闭区间的二分）

var arrangeCoins = function (n) {
    let left = 1,
        right = n;

    while (left <= right) {
        const mid = left + (right - left) >> 1;
        // 当 小于等于的时候成立
        if (mid * (mid + 1) / 2 <= n) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    // 由于成立的时候，多加了一次 1，此处减掉
    return left - 1;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
评论

中午好👏🏻，我是 ✍🏻   疯狂 codding 中...

粽子

这有关于前端开发的技术文档和你分享。

相信你可以在这里找到对你有用的知识和教程。

了解更多

目录

  1. 1. 排列硬币
  2. 2. 解题思路：
  3. 3. 复杂度：
  4. 4. 代码实现：（左闭右闭区间的二分）