# LeetCode Medium 162. Find Peak Element

tags: leetcode

問題

• Explore
• Problems

今回からいらないかなということで問題文は省きます

アイデア

peak elementという隣の要素よりも大きい要素を探すという問題です. ただし, どのpeak elementでも良いです

対数時間で計算する必要があります

下の図のようにPeakとなる点の種類は分けられます

1. 単調に増加する点の終点
2. 単調に減少する点の始点
3. その点を境に増減する点

この単調性を利用して二分探索を利用して解けるという発想になります

解法1(recursive)

1のパターンのときと2のパターンのときは単に真ん中の要素が下り坂にあるかどうかを見てそれに応じて探索する範囲を制限すれば良いです

3のパターンも, 見た目は違いますが, 同じようにして探索する範囲を狭めていけば良いです

• 探索する範囲の中央をmidとします
• midの要素がmid+1の要素よりも大きい時はこの値の左側にpeak elementがある可能性があるので左側を探索します
• そうでないときは右側にpeak elementがあるので右側を探索します

計算量

配列の長さを$N$とします. 再帰は最大で深さが$\log N$に比例した深さとなります

• 時間計算量
  • $O(\log N)$
• 空間計算量
  • $O(\log N)$

C++

解法2(iterative)

上で書いたコードを反復的に書くのみです

計算量

再帰関数を使わない分, 空間計算量を抑えることが可能です

• 時間計算量
  • $O(\log N)$
• 空間計算量
  • $O(1)$

C++

class Solution {
public:
  int findPeakElement(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
      int mid = left + (right - left) / 2;
      if (nums[mid] > nums[mid + 1])
        right = mid;
      else
        left = mid + 1;
    }
    return left;
  }
};