局部最小值问题

局部最小值问题

自写：

	// arr 相邻的数不相等！ 返回一个局部最小的下标
    public static int oneMinIndex(int[] arr) {
        if(arr == null || arr.length == 0) {
            return -1;
        }
        if(arr.length == 1) {
            return 0;
        }
        int L = 0;
        int R = arr.length - 1;
        if(arr[L] < arr[L + 1]) {
            return L;
        }
        if(arr[R] < arr[R - 1]) {
            return R;
        }
        // 之后是两边下陷的情况
        while(L <= R) {
            int mid = (L + R) / 2;
            if (mid -1 >= L && mid +1 <= R && arr[mid] < arr[mid + 1] && arr[mid] < arr[mid - 1]) {
                return mid;
            }
            if(mid -1 >= L && arr[mid] > arr[mid - 1]) {
                R = mid - 1;
                continue;
            }
            if(mid +1 <= R && arr[mid] > arr[mid + 1]) {
                L = mid + 1;
            }
            // L与R相邻的时候，直接返回最小的那个
            if(mid == L || mid == R) {
                return arr[L] > arr[R] ? R : L;
            }
        }
        return -1;
    }
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

左神：

// arr 相邻的数不相等！ 返回一个局部最小的下标
    public static int oneMinIndex2(int[] arr) {
        if(arr == null || arr.length == 0) {
            return -1;
        }
        if(arr.length == 1) {
            return 0;
        }
        int L = 0;
        int R = arr.length - 1;
        if(arr[L] < arr[L + 1]) {
            return L;
        }
        if(arr[R] < arr[R - 1]) {
            return R;
        }
        // 之后是两边下陷的情况
        while(L < R-1) {
            int mid = (L + R) / 2;
            if (arr[mid] < arr[mid + 1] && arr[mid] < arr[mid - 1]) {
                return mid;
            }
            if(arr[mid] > arr[mid - 1]) {
                R = mid - 1;
                continue;
            }
            if(arr[mid] > arr[mid + 1]) {
                L = mid + 1;
            }
        }
        return arr[L] < arr[R] ? L : R;
    }
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

总结一下：

	public static int oneMinIndex3(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int N = arr.length;
        if (N == 1) {
            return 0;
        }
        //到这，arr的长度是大于等于2的
        if (arr[0] < arr[1]) {
            return 0;
        }
        if (arr[N - 1] < arr[N - 2]) {
            return N - 1;
        }
        int L = 0;
        int R = N - 1;
        int ans = -1;
        while (L <= R) {
            int mid = (L + R) / 2;
            //中间位置是否是最小，[mid-1] > [mid] < [mid+1]
            if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
                ans = mid;
                break;

                //不同时小，下面两个判断选一个就行
            } else if (arr[mid] > arr[mid - 1]) {
                R = mid;
            } else {//arr[mid] > arr[mid + 1]
                L = mid;
            }
        }
        return ans;
    }
}
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

L == 0 ，R == n - 1

0 与 n - 1位置上一定不是局部最小值，而 [ 1 , n-2 ] 之间一定有局部最小值，所以 mid (mid：锁定局部最小

值的)不可能来到下标 0 与 n - 1 的位置，下标 0 与 n - 1 作为一个缓冲区（如果来到0或n-1的旁边，0与n - 1

可作为一个缓冲区，就不会出现mid-1或者mid+1越界的情况）。如果mid位置是局部最小值就返回了，如果没

返回说明mid位置不是局部最小值，我们就令L == mid 或者是 R == mid，这样 L 与 R 也是一个缓冲区，L与R

之间一定有局部最小值。还有就是，不会有(L == 0&& R == 1 ) || (L == N-2 && R == N-1 )

的情况，如果出现上述的情况说明一定没有局部最小值（L与R是缓冲区，中间没有值），然而事实是一定有

局部最小值。

这个方法的关键是：下标0，N-1的区域做缓冲区，L与R做缓冲区。所以没有越界的风险。

	public static int getLessIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        if (arr.length == 1 || arr[0] < arr[1]) {
            return 0;
        }
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }
        int left = 1;
        int right = arr.length - 2;
        int mid = 0;
        while (left <= right) {
            mid = (left + right) / 2;
            if (arr[mid] > arr[mid - 1]) {
                right = mid - 1;
            } else if (arr[mid] > arr[mid + 1]) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        // 这个地方return谁都是对的，因为一定有区域最小值
        return left; 
    }
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

L == 1 ，R == n - 2

如果mid位置是局部最小值就返回了，如果没返回说明mid位置不是局部最小值，我们就

令L == mid + 1 或者是 R == mid - 1，mid一定不是局部最小值，但是mid+1与mid-1可能是局部最小值。所以

【L，R】L与R之间都是 “好的” 都是有可能是局部最小值的区域，剔除不是局部最小值的部分，在是局部最小

值的区域寻找。

这个方法的关键：[L , R] L与R之间都是“好的”部分（可能是局部最小值的部分）不可能来到下标 0，n - 1位

置，并且下标 0，n - 1位置可以作为一个缓冲，所以不会出现越界的状况。

// arr 相邻的数不相等！ 返回一个局部最小的下标
    public static int oneMinIndex(int[] arr) {
        if(arr == null || arr.length == 0) {
            return -1;
        }
        if(arr.length == 1) {
            return 0;
        }
        int L = 0;
        int R = arr.length - 1;
        if(arr[L] < arr[L + 1]) {
            return L;
        }
        if(arr[R] < arr[R - 1]) {
            return R;
        }
        // 之后是两边下陷的情况
        while(L <= R) {
            int mid = (L + R) / 2;
            if (mid -1 >= L && mid +1 <= R && arr[mid] < arr[mid + 1] && arr[mid] < arr[mid - 1]) {
                return mid;
            }
            if(mid -1 >= L && arr[mid] > arr[mid - 1]) {
                R = mid - 1;
                continue;
            }
            if(mid +1 <= R && arr[mid] > arr[mid + 1]) {
                L = mid + 1;
            }
            // L与R相邻的时候，直接返回最小的那个
            if(mid == L || mid == R) {
                return arr[L] > arr[R] ? R : L;
            }
        }
        return -1;
    }
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

L == 0 R == n - 1

下标为0 和 n - 1的位置是一个缓冲区。

如果mid位置是局部最小值就返回了，如果没返回说明mid位置不是局部最小值，我们就

令L == mid + 1 或者是 R == mid - 1。

刚开始L == 0，R == n - 1是一个缓冲区，仅当R == mid - 1的时候，R失去了缓冲区的作用，但是L仍然是缓冲

区，因为R是“好的”，所以当R来到下标为1的位置就会出现越界的风险，因为此时mid指向L，即0下标。

而上面的方法1不会有问题的原因是：L与R都是缓冲区，不会有(L == 0&& R == 1 ) || (L == N-2 && R == N-1 )

的情况，如果出现上述的情况说明一定没有局部最小值（L与R是缓冲区，中间没有值），然而事实是一定有

局部最小值。

而本方法就会有(L == 0&& R == 1 )的情况出现，因为R 不是缓冲区。一遍是缓冲区一遍不是缓冲区，就有可

能越界。

写代码的时候别写方法三这种半吊子代码。