162 尋找峰值

直接貪心

?public?int?findPeakElement(int[]?nums)?{

????????int?idx?=?0;

????????for?(int?i?=?1;?i?<?nums.length;?++i)?{

????????????if?(nums[i]?>?nums[idx])?{

????????????????idx?=?i;

????????????}

????????}

????????return?idx;

????}

遍歷一次保存最大值的下標(biāo)。

方法二：迭代爬坡

class Solution {

? ? public int findPeakElement(int[] nums) {

? ? ? ? int n = nums.length;

? ? ? ? int idx = (int) (Math.random() * n);

? ? ? ? while (!(compare(nums, idx - 1, idx) < 0 && compare(nums, idx, idx + 1) > 0)) {

? ? ? ? ? ? if (compare(nums, idx, idx + 1) < 0) {

? ? ? ? ? ? ? ? idx += 1;

? ? ? ? ? ? } else {

? ? ? ? ? ? ? ? idx -= 1;

? ? ? ? ? ? }

? ? ? ? }

? ? ? ??

? ? ? ? return idx;

? ? }

? ? // 輔助函數(shù)，輸入下標(biāo) 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;

? ? }

}