ピークを見つける

問題ではピーク要素とは左右の隣接要素より大きいもので、nums[-1]=nums[n]=-∞とも書いてあるので、nums[0]がnums[1]より大きいかどうかのハントで、nums[-1]が負の無限大ならnums[0]がピーク要素になるのでは？

nums[0] が nums[1] よりも大きくない場合は、そのまま nums[1] と nums[2] を比較し、nums[1] の方が大きければ、nums[1] がピーク要素であると仮定することもできます。nums[1] が nums[2] よりも大きくない場合は、後ろを振り返り続けます。

この方法の時間的複雑さはO(n)です。

class Solution {
public:
 int findPeakElement(vector<int>& nums) {
 for(int i = 0; i < nums.size() - 1; ++i) {
 if(nums[i] > nums[i + 1]) {
 return i;
 }
 }
 return 0;
 }
};

この問題では、O(logn)の時間複雑度を持つ解が求められています。それなら、バイセクションを使うしかありません。

一般に、二等分法は順序配列の要素を見つけるために使われますが、ここでは順序配列ではありません。

この問題では、nums[-1] = nums[n] = -∞ となっており、さらにこの問題の要素はすべて同じではないので、隣接するすべての要素よりも大きい要素があるはずです。配列の要素が増加する場合でも、最後の要素がピーク要素であり、減少することは同じです。ですから、この問題には解があることが保証されています。

もし nums[mid] < nums[mid + 1]であれば、右半分にピークがあるはずです。nums[mid + 1]はmidより大きく、nums[n]は負の無限大ですから、右半分は上昇と下降を繰り返しているはずです。右半分が上昇し、右半分が下降しているように見えるはずなので、left = mid + 1 とします（最小のピークも nums[mid + 1] です）。

同様に、nums[mid] > nums[mid + 1]の場合、nums[mid]はnums[mid + 1]より大きく、nums[0]は負の無限大なので、区間の左半分にピークがあるはずです。

ルックアップを毎回半分に折りたたむと、ピークエレメントが出来上がります。

コードは以下の通り：

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