闲来无事刷道题呗。
题目介绍
简单的说，假如你有 N 枚硬币，需要摆成阶梯的形式，即第 N 行一定有 N 个硬币。求最多能摆多少行。
题目分析
最直观的解法，因为我们知道第 N 行必须要需要 N 个硬币。所以我们只要从第一行开始，每加一行减掉对应所需 X 个。什么时候总数不够了，那么游戏到此结束。
解法一
/** * @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; }
