java局部最小值问题（超详细解题思路）

秒速五厘米 2024-04-03 08:58 49阅读 0赞

**目录**

问题描述：

局部最小值描述：

举例：

实现思路：

实现代码：

--------------------

### 问题描述： ###

在一个所有数值都不相等的数组中找到任意一个“局部最小值”，时间复杂度要求小于O(N)。

#### 局部最小值描述： ####

一、数组第一个小于第二个时，第一个即局部最小值，数组最后一个小于倒数第二个时，最后一个即局部最小值。

二、一个数小于左右两边的数时，这个数为局部最小值。

#### 举例： ####

\{2,9,1,7,6,5,4,3\}，N=8，其中2、1和3均为局部最小值，返回任意一个就行。

### 实现思路： ###

这是一道在数组中找数的题，即**查找**，我们可以先观察数据的规律，然后试着通过规律寻找办法。

首先我们可以知道有两种情况，第一种是，已知可直接返回数值的情况，即数组最左边或最右边满足小于旁边的数时可以直接返回这个局部最小值。

第二种情况是不满足第一种情况的情况，即最左和最右的数是大于旁边的数。

以上是可以直接获得的信息，通过结合“**第二种情况**”和题目给出的“**所有的数不相等**”，我们可以从数字转看到图像，发现这个数组在直角坐标系中的一个规律，即最数组下标0到下标1的位置的在坐标系中呈现的图像是下降的，N-2到N-1所呈现的是上升的，在\[1,N-2\]中是上下必有波动的，所以必有一个局部最小值。

通过以上分析我们可以知道它的规律是“波动”，既然是查找，可以思考一下是否可以构建一个左或右半部分缩进的逻辑。

答案是可以的，所以有**规律+有两侧缩进逻辑=可以使用二分查找**

### 实现代码： ###

public class Practice {
        public static int minProblem(int[] arr) {
            int N = arr.length;
            if (arr[0] < arr[1]) {
                return 0;
            }
            if (arr[N - 1] < arr[N - 2]) {
                return N - 1;
            }
    
            int mid = 0, l = 1, r = N - 2;
            //l和r直接把界线缩在[1,N-2]上，因为如果运行到这里，0和N-1肯定不符合条件，所以直接pass
    
            while (l <= r) {//这里的<=是因为[1,N-2]是闭区间，所以有可能缩到界线相等，所以才用=号
                mid = l + ((r - l) >> 1);//一种防止加法溢出的写法。（位运算比除法快，>>1等价与/2）
    
                if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
                    return mid;//符合中间数是局部最小值即返回
                } else if (arr[mid] > arr[mid - 1]) {
                    r = mid - 1;//mid部分不是局部最小值，所以多缩1范围，始终保持闭区间
                } else if (arr[mid] > arr[mid + 1]) {
                    l = mid + 1;//mid部分不是局部最小值，所以多缩1范围，始终保持闭区间
                }
            }
            return -1;//不会运行到这里，为了让代码通过，随意加了个return
        }
    
    
        //测试运行，输出一个局部最小值
        public static void main(String[] args) {
            //int[] arr = {6, 2, 3, 4, 5, 9,10};
            int[] arr = {10,9,1,7,6,5,4,11};
            System.out.println(arr[minProblem(arr)]);
        }
    
    
    }

如有错误思想，还望多多指正，感激不尽！