31. 下一个排列

<?php
class Solution {
    /**
     * @param Integer[] $nums
     * @return array
     */
    function nextPermutation(&$nums) {
        if (!$nums || count($nums) == 1) {
            return $nums;
        }
        // 从右往左，找到第一个逆序元素 $reverse
        $reverse = count($nums) - 1;
        for ($i = $reverse; $i > 0; $i--) {
            if ($nums[$i] > $nums[$i - 1]) {
                $reverse = $i - 1;
                break;
            }
        }
        // 从右往左，找到大于 $reverse 且 最接近 $reverse 的元素 $close
        if (($close = $reverse + 1) < (count($nums) - 1)) {
            for ($j = $reverse + 1; $j < count($nums); $j++) {
                if ($nums[$j] < $nums[$reverse]) {
                    continue;
                }
                $close = ($nums[$j] - $nums[$reverse]) < ($nums[$close] - $nums[$reverse]) ? $j : $close;
            }
        }
        // 交换 $reverse 和 $close
        $tmp = $nums[$reverse];
        $nums[$reverse] = $nums[$close];
        $nums[$close] = $tmp;
        // 翻转 $reverse 右边的元素
        $tmp1 = array_slice($nums, 0, $reverse + 1);
        $tmp2 = array_reverse(array_slice($nums, $reverse + 1));
        $nums = array_merge($tmp1, $tmp2);
        return $nums;
    }
}
/**
 * 1,2,3 → 1,3,2
 * 3,2,1 → 1,2,3
 * 1,1,5 → 1,5,1
 *
 * 1,5,8,4,7,6,5,3,1 → 1,5,8,4,7,6,5,3,1
 * 1,5,8,4,7,6,5,3,1 → 1,5,8,5,7,6,4,3,1
 * 1,5,8,5,7,6,4,3,1 → 1,5,8,5,1,3,4,6,7
 */
$nums = [1,5,8,4,7,6,5,3,1];
$cls = new Solution();
$ret = $cls->nextPermutation($nums);
echo implode(',', $ret);