Leetcode # 852. Peak Index in a Mountain Array

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

Solution

如果只用三點來判斷是否為 mountain array
容易發生如上圖的誤判

所以使用斜率，來判斷中點位於上坡或下坡

Time Complexity: O(log(len(arr)))
Space Complexity: O(1)

class Solution:
  def peakIndexInMountainArray(self, arr: List[int]) -> int:
    l, r = 0, len(arr) - 1
    while l < r:
      m = (l + r) // 2
      if arr[m] < arr[m + 1]:
        l = m + 1
      else:
        r = m
    return l

Last Updated on 2023/08/16 by A1go