Leetcode -162- Look for peaks

[Blog link]

The path to learning at 🐔

The nuggets home page

[答 案]

Topic link

[making address]

Making the address

[B].

Peak elements are those whose values are strictly greater than their left and right neighbors.

Given an integer array nums, find the peak element and return its index. The array may contain multiple peaks, in which case you simply return the location of any one of the peaks.

You can assume that NUMs [-1] = nums[n] = -∞.

You have to implement order log n time to solve this problem.

 

Example 1:

Input: nums = [1,2,3,1] output: 2 explanation: 3 is the peak element, and your function should return its index 2.Copy the code

Example 2:

Input: nums = [1,2,1,3,5,6,4] Or return index 5 with a peak element of 6.Copy the code

Idea 1: binary search + greedy

  • The first response to LGN time complexity is binary search
  • How to find the peak element in binary
  • The proof of the greedy method can be divided into two steps
    • Step one: Can we prove itAn array must have a peak element
      • Because there are two negative infinity boundaries
      • So when there’s only one element in the array that element is the peak element
      • When the array length is greater than 1
      • Without loss of generality, x[I] is the left boundary element, and if x[I]>x[I +1] then I is the peak element index
      • If x[I]
      • Follow this logic and move right I until you reach an x[I]>x[I +1] and you find the peak element
      • If this is not the case until I +1 reaches the right boundary, then x[I +1] must be greater than the boundary of negative infinity
      • So the last element is the peak element
    • The second step proves that the dichotomy does not miss the peak element
      • When x[I]>x[i-1] then the peak element must appear in x[I] itself or to the right
      • This point is easy to understand from proof one
      • Because this is the case where x[I] is less than x[I +1], you have to have a peak element on the right-hand side
      • Conversely, if x[I]>x[I +1], it must appear in x[I] itself or to the left
      • And the same argument goes up here
      • Next up is the regular binary template
      • We’re dichotomized not for order, but for duality
      • Use dichotomy only if each paragraph is different
public int findPeakElement(int[] nums) {
   int l = 0, r = nums.length - 1;
   if (r == 0) {
       return 0;
   }
   while (l < r) {
       int mid = l + r + 1 >> 1;
       if (mid == 0) {
           if (nums[mid] > nums[mid + 1]) {
               return 0;
           } else {
               l = mid + 1; }}else if (mid > 0 && mid < nums.length - 1) {
           if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {
               return mid;
           }
           if (nums[mid] > nums[mid - 1]) {
               l = mid;
           } else {
               r = mid - 1; }}else {
           return nums[mid] > nums[mid - 1]? mid : mid -1; }}return l;
}
Copy the code
  • Time complexity O(LGN)
  • Space complexity O(1)