Question

Formatted question description: https://leetcode.ca/all/162.html

 162. Find Peak Element

 A peak element is an element that is greater than its neighbors.

 Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

 The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

 You may imagine that nums[-1] = nums[n] = -∞.

 Example 1:

 Input: nums = [1,2,3,1]
 Output: 2
 Explanation: 3 is a peak element and your function should return the index number 2.

 Example 2:

 Input: nums = [1,2,1,3,5,6,4]
 Output: 1 or 5
 Explanation: Your function can return either index number 1 where the peak element is 2,
                or index number 5 where the peak element is 6.

 Note:
    Your solution should be in logarithmic complexity.

 @tag-array

Algorithm

If you traverse the entire array to find the maximum value here, Time Limit Exceeded will definitely appear, but the title says that this peak can be a local maximum, so we only need to find the first local peak.

The so-called peak value is a number that is larger than the surrounding two numbers, so you only need to compare it with the surrounding two numbers.

  • Since you want to compare with the left and right numbers, you have to consider the problem of out-of-bounds. The title gives nums[-1] = nums[n] = -∞, then add these two integer minimums directly to the array, and then Traverse from the second number to the penultimate number, so that there is no possibility of crossing the boundary.
  • Since the question says that the peak must exist, there is a very important corner case that we should pay attention to, that is, when there is only one number in the original array, and it is the minimum value of an integer, if we have to add numbers at the beginning and end, A horizontal line will be formed, and there will be no peak value, so we directly judge the situation that there is only one number in the array at the beginning

Then, based on idea above, you can omit the step of padding the first and last values, and you can traverse from the second number to the next,

  • If the second number is smaller than the first number, it means that the first number is a local peak at this time;
  • Otherwise, it will continue to traverse back, and now it is an increasing trend. If a certain number is less than the previous number at this time, it means that the previous number is a local peak, just return to the position.
  • If the loop ends, it means that the original array is an increasing array, just return to the last position

Code

Java

public class Find_Peak_Element {

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

    class Solution {
        public int findPeakElement(int[] nums) {
            if (nums.length == 1) return 0;
            int[] newNums = new int[nums.length + 2];
            System.arraycopy(nums, 0, newNums, 1, nums.length);
            newNums[0] = Integer.MIN_VALUE;
            newNums[newNums.length - 1] = Integer.MIN_VALUE;
            for (int i = 1; i < newNums.length - 1; ++i) {
                if (newNums[i] > newNums[i - 1] && newNums[i] > newNums[i + 1]) return i - 1;
            }
            return -1;
        }
    }

    public class Solution_binary {
        public int findPeakElement(int[] nums) {
            int l = 0, r = nums.length - 1;

            // Compare the size with the immediately following element. If it is larger, the peak value is in the front, and if it is smaller, it is in the back. So you can find a peak
            while (l < r) {
                int mid = (l + r) / 2;
                if (nums[mid] > nums[mid + 1])
                    r = mid;
                else
                    l = mid + 1;
            }
            return l;
        }
    }
}

All Problems

All Solutions