LeetCode/MD.php at master · Kanon11/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
<?php
class solution
{
    // function maximumGap($a) //O(n^2)
    // {
    //     $n = count($a);
    //     if ($n == 1) {
    //         return 0;
    //     }
    //     $maxji = 0;
    //     for ($i = 0; $i < $n; $i++) {
    //         for ($j = $i + 1; $j < $n; $j++) {
    //             if ($a[$i] <= $a[$j]) {
    //                 $temp = $j - $i;
    //                 if ($temp > $maxji) {
    //                     $maxji = $temp;
    //                 }
    //             }
    //         }
    //     }
    //     return $maxji;
    // }
    function maximumGap($a) // O(Nlogn)
    {
        $aa = [];
        foreach ($a as $key => $value) {
            $x = [$value, $key];
            $aa[] = $x;
        }
        sort($aa);
        $md = PHP_INT_MIN;
        for ($i = 1; $i < count($aa); $i++) {
            $temp = $aa[$i][1] - $aa[$i - 1][1];
            if ($temp > $md) {
                $md = $temp;
            }
        }
        return $md;
    }
}

$obj = new solution();
$a = [1, 10, 30, 20];
echo "<pre>";
print_r($obj->maximumGap($a));
echo "</pre>";