Shulou(Shulou.com)06/01 Report--

This article is to share with you about how LeetCode looks for peaks. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

Topic description

A peak element is an element whose value is greater than its left and right adjacent values.

Given an input array nums, where nums [I] ≠ nums [item1], find the peak element and return its index.

The array may contain multiple peaks, in which case you can return to the location of any peak.

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

Example 1:

Output: 2 explanation: 3 is the peak element, your function should return its index 2.

Example 2:

Output: 1 or 5 explanation: your function can return index 1 with its peak element 2, or index 5 with its peak element 6.

Description:

Your solution should be O (logN) time complexity.

The idea of solving the problem

Tags: binary search

Process:

First of all, we should pay attention to the condition of the topic. Nums [- 1] = nums [n] =-∞ appears in the topic description, which means that as long as there is an element in the array that is larger than the adjacent elements, then a peak can be found along it.

Based on the above conclusion, we can use binary search to find the peak.

When looking up, the left pointer l, the right pointer r, with the order of the left and right as the loop condition

The middle position m is calculated according to the left and right pointer, and the values of m and m are compared. If m is larger, there is a peak on the left side, and there is a peak on the right side, l=m+1.

Time complexity: O (logN)

Algorithm dynamic graph code class Solution {public int findPeakElement (int [] nums) {int left = 0, right = nums.length-1; for (; left

Nums [mid + 1]) {right = mid;} else {left = mid + 1;}} return left;}} Thank you for reading! This is the end of this article on "how to find a peak in LeetCode". I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, you can share it for more people to see!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.