278.md

✏️Leetcode之PHP版题目解析（441. Arranging Coins)

2020-07-12 吴亲库里 库里的深夜食堂

---

✏️描述

简单的说，假如你有 N 枚硬币，需要摆成阶梯的形式，即第 N 行一定有 N 个硬币。求最多能摆多少行

---

✏️题目实例

​ ****

✏️题目分析

最直观的解法，因为我们知道第 N 行必须要需要 N 个硬币。所以我们只要从第一行开始，每加一行减掉对应所需 X 个。什么时候总数不够了，那么游戏到此结束。

✏️代码实现1

/**
     * @param Integer $n
     * @return Integer
     */
    function arrangeCoins($n)
{
        $i = 1;
        if ($n == 0) return 0;
        while ($n > 0) {
            $n -= $i;
            $i++;
            if ($n < $i) return $i - 1;
        }
    }

这种解法时间复杂度 O (n)，空间复杂度 O (1)。空间复杂度无需再优化了，可以看看能否在时间上动动手脚。

✏️解法二

这时间上优化先看看从 O (n) 到 O (log2n) 。台阶 1-n ，本质上就是一个有序的集合，既然是有序，当然就可以用到 Binary Search 的思想。每次找到中位数，计算中位数 m (即第 m 行) 所需要的硬币总和和给定的硬币数进行比较，不断压缩空间。

/**
     * @param Integer $n
     * @return Integer
     */
    function arrangeCoins($n)
    {
        $left = 0;
        $right = $n;
        while ($left < $right) {
            $middle = $left + (($right - $left + 1) >> 1);
            //$middleSum=($middle*$middle+$middle)/2;
            $middleSum = $middle * ($middle + 1) / 2;
            if ($middleSum <= $n) {
                $left = $middle;
            } else {
                $right = $middle - 1;
            }
        }
        return $left;
    }

联系

​