Pythonでピーク要素を見つける

配列内のピーク要素を見つける必要があるとします。ピーク要素は、隣接する要素よりも大きい要素です。入力配列numsがあり、nums[i]≠nums[i + 1]であるとすると、ピーク要素を検索してそのインデックスを返します。配列は複数のピーク要素を保持できます。その場合、インデックスはピーク要素のいずれかに返されます。 nums [-1] =nums[n]=-∞と想像できます。したがって、配列が[1,2,1,3,5,6,4]のような場合、ピーク要素は1または5である必要があります。

これを解決するには、次の手順に従います-

• low：=0およびhigh：=配列の最後のインデックス、n：=配列のサイズ、ans：=無限大
• 低い<=高い
  • 中：=低+（高-低）/ 2
  • mid – 1>=0およびnums[mid– 1] <=nums [mid]の場合、low：=mid、それ以外の場合はhigh：=mid-1
• 低く戻す

理解を深めるために、次の実装を見てみましょう-

例

class Solution(object):
   def findPeakElement(self, nums):
      low = 0
      high = len(nums)-1
      while low<high:
         mid = low + (high - low+1)//2
         if (mid-1>=0 and nums[mid-1]<=nums[mid]):
            low = mid
         else:
            high = mid-1
      return nums[low+1]
ob1 = Solution()
print(ob1.findPeakElement([15,35,85,96,5,6,8,12]))

入力

[15,35,85,96,5,6,8,12]

出力

5