Skip to content

Latest commit

 

History

History
98 lines (64 loc) · 2.32 KB

852.Peak_Index_in_a_Mountain_Array.md

File metadata and controls

98 lines (64 loc) · 2.32 KB
Raw
  1. Peak Index in a Mountain Array

简单

https://leetcode-cn.com/problems/peak-index-in-a-mountain-array/

Let's call an array arr a mountain if the following properties hold:

arr.length >= 3

There exists some i with 0 < i < arr.length - 1 such that:

arr[0] < arr[1] < ... arr[i-1] < arr[i]
arr[i] > arr[i+1] > ... > arr[arr.length - 1]


Given an integer array arr that is guaranteed to be a mountain, return any i such that arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1].

 

Example 1:

Input: arr = [0,1,0]
Output: 1

Example 2:

Input: arr = [0,2,1,0]
Output: 1

Example 3:

Input: arr = [0,10,5,2]
Output: 1

Constraints:

3 <= arr.length <= 104
0 <= arr[i] <= 106
arr is guaranteed to be a mountain array.

Follow up:

Finding the O(n) is straightforward, could you find an O(log(n)) solution?

相关企业

  • 亚马逊 Amazon|6
  • 谷歌 Google|5
  • 彭博 Bloomberg|4
  • Facebook|2

相关标签

  • Array
  • Binary Search

相似题目

  • Find Peak Element 中等

Sol

二分法，判断山脉趋势，按照取数递归左边或者右边即可。 山顶的条件是第一个使得 nums[i] > nums[i + 1] 的 i。 当然也可以反过来，最后一个使得 nums[i] > nums[i - 1] 的 i

from typing import (
    List,
)

```py
class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        if not arr:
            return -1

        start, end = 0, len(arr) - 1

        while start + 1 < end:
            mid = start + (end - start) // 2
            if arr[mid] < arr[mid+1]:
                start = mid 
            else:
                end = mid 
        if arr[start] >= arr[end]:
            return start
        return end

如果你解决了这道题，你会发现，二分问题其实并不需要要求数组一定是严格有序的，我们不能根据数组是否有序来判断是否是二分问题。

那我们该如何判断这个问题是否是二分问题呢？

一个判断算法的技巧——通过时间复杂度判断算法。。我们知道二分答案的时间复杂度是O(logn)的。所以当你发现有一个问题，用O(N)的时间复杂度非常好做，或者面试官说：“你给我优化一下这个算法。”那么你优化的思路就是优化到O(logn)，也就是尝试使用二分去做，这就是二分算法的判断条件.