162. 寻找峰值

leetcode链接：
https://leetcode.cn/problems/find-peak-element/description/

方案一

int left = 0,
	right = nums.length,
	mid = 0;
if (right == 1)
	return 0; 
if (nums[0] > nums[1]) 
	return 0;
if (nums[right - 1] > nums[right -2])
	return right - 1;
while (left < right) {
	mid = left + (right - left) / 2;
	if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {
		return mid;
	} else if (nums[mid] < nums[mid + 1]) {
		left = mid;
	} else {
		right = mid;
	}
}
return 0;

结果

• 65/65 cases passed (0 ms)
• Your runtime beats 100 % of java submissions
• Your memory usage beats 89.62 % of java submissions (40.6 MB)

分析

时间复杂度：
O( log n )

空间复杂度：
O( 1 )

几乎最优方案

https://leetcode.cn/problems/find-peak-element/solution/xun-zhao-feng-zhi-by-leetcode-solution-96sj/

class Solution {
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        int left = 0, right = n - 1, ans = -1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (compare(nums, mid - 1, mid) < 0 && compare(nums, mid, mid + 1) > 0) {
                ans = mid;
                break;
            }
            if (compare(nums, mid, mid + 1) < 0) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }

    // 辅助函数，输入下标 i，返回一个二元组 (0/1, nums[i])
    // 方便处理 nums[-1] 以及 nums[n] 的边界情况
    public int[] get(int[] nums, int idx) {
        if (idx == -1 || idx == nums.length) {
            return new int[]{0, 0};
        }
        return new int[]{1, nums[idx]};
    }

    public int compare(int[] nums, int idx1, int idx2) {
        int[] num1 = get(nums, idx1);
        int[] num2 = get(nums, idx2);
        if (num1[0] != num2[0]) {
            return num1[0] > num2[0] ? 1 : -1;
        }
        if (num1[1] == num2[1]) {
            return 0;
        }
        return num1[1] > num2[1] ? 1 : -1;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/find-peak-element/solution/xun-zhao-feng-zhi-by-leetcode-solution-96sj/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。