leetcode Java：162. 尋找峰值

題目：162. 尋找峰值

思路：

題目有一點很重要：對于所有有效的

i

都有

nums[i] != nums[i + 1]

。

同時，峰值隻要求大于相鄰的數。

線性查找：從頭開始，隻需要判斷是否大于下一個數；如果不大于下一個數，那麼我們會繼續查找，也就是說，隻要來到了目前位置，就已經保證了目前位置大于前一個位置。

二分：找出中點

mid

，判斷

mid

與

mid+1

處值的大小

如果

nums[mid] > nums[mid + 1]

：說明峰值在左區間，我們更新右區間為

mid

；

如果

nums[mid] < nums[mid + 1]

：說明峰值在右區間，我們更新左區間為

mid+1

。

代碼：線性查找

class Solution {
    public int findPeakElement(int[] nums) {
        for (int i = 0; i < nums.length - 1; i ++) {
            if (nums[i] > nums[i + 1]) {
                return i;
            }
        }
        return nums.length - 1;
    }
}
           

代碼：二分

class Solution {
    public int findPeakElement(int[] nums) {
        return binary(0, nums.length - 1, nums);
    }
    public int binary(int l, int r, int[] nums) {
        if (r == l) {
            return l;
        }
        int mid = (l + r) / 2;
        if (nums[mid] > nums[mid + 1]) {
            r = mid;
        }
        if (nums[mid] < nums[mid + 1]) {
            l = mid + 1;
        }
        return binary(l, r, nums);
    }
}