Find Peak Element
配列 nums は増加した後に減少します。あるインデックスまでは各値がその直前の値より大きく、そのインデックス以降は各値がその直前の値より小さくなります。どちらかの部分は空でもよいため、配列は増加するだけ、または減少するだけの場合もあります。折り返し位置の値がピークであり、隣接するすべての値より大きい唯一の値です。
O(log n) 時間でピークのインデックスを返してください。
関数
- numsinteger-array
- 値が上昇して1つのピークに達し、その後下降する
- 戻り値integer
- ピークのインデックス
制約
1 ≤ nums.length ≤ 5000-106 ≤ nums[i] ≤ 106nums[i] != nums[i+1]が有効なすべてのiに対して成り立つ。numsはある1つのインデックスまで厳密に増加し、その後は厳密に減少するため、ピークはちょうど1つです。
例
- 入力
- nums = [2, 5, 9, 4, 1]
- 出力
- 2
- 説明
- 値は2、5、9と増加し、その後4、1と減少します。転換点は9で、インデックスは2です。
- 入力
- nums = [8, 6, 3, -2]
- 出力
- 0
- 説明
- 配列は減少するだけなので、登る部分はなく、頂点は最初の値である、インデックス0の8です。
- 入力
- nums = [-7, -3, 0, 12, 40]
- 出力
- 4
- 説明
- 配列は増加するだけなので、最大値は最後の値である、インデックス4の40です。負の値は何も変えません。
発展問題
隣接するどの2つのセルも等しくないグリッドでは、ピークとは、上下左右の最大4つの隣接セルより大きいセルのことです。すべてのセルを調べずにピークを見つけられますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
任意のインデックス
midを選び、nums[mid+1]を見てみましょう。その一歩の方向から、ピークがどこにあるかについて何がわかりますか？ステップアップが起こるのはピークの前だけで、ステップダウンが起こるのはピークまたはその後だけです。したがって、1回の比較で
midの片側を除外できます。ピークを常に含む範囲を保ちます。上向きのステップでは
loをmid+1に移動し、そうでなければhiをmidに移動します。両者が一致したら終了します。
解説
ピークが1つだけの場合、ピークは最大値なので、1回の走査で O(n) で見つけられます。O(log n) を実現するには、nums[mid] と nums[mid+1] を比較します。mid における傾きから、ピークがどちら側にあるかがわかるため、各ステップで範囲を半分に絞れます。
値が下がり始めるまで進みます
考え方
ピークより前では、すべての値が次の値より小さく、ピーク以降では、すべての値が次の値より大きくなります。したがって、ピークは nums[i] > nums[i+1] となる最初のインデックス i、または配列が単調に増加するだけの場合は最後のインデックスです。
5000 個の値の末尾にピークがある場合、順に調べると 4999 回比較しますが、二分探索なら 13 回で済みます。
アルゴリズム
iを 0 から n-2 まで変化させ、nums[i]とnums[i+1]を比較します。nums[i]のほうが大きい最初のiで、iを返します。- 減少がないままループが終了した場合は、
n-1を返します。
def findPeakElement(nums):
for i in range(len(nums) - 1):
if nums[i] > nums[i + 1]:
return i # the first step down starts at the peak
return len(nums) - 1 # never went down: the last value is the peak傾きに対する二分探索
考え方
1組のペア、nums[mid] と nums[mid+1] を読み取ります。値が上がっていれば、配列はまだ上昇中です。この配列では山頂より前でのみ起こるため、山頂は mid+1 またはその右側にあります。値が下がっていれば、山頂にいるか、山頂を過ぎています。つまり、山頂は mid またはその左側にあります。
常に山頂を含む範囲 [lo, hi] を保ちます。値が上がっていれば、lo を mid+1 に移動します。値が下がっていれば、hi を mid に移動します。mid が山頂である可能性があるため、範囲に残します。lo と hi が一致すると、残ったインデックスが山頂です。mid を切り下げることで hi より小さく保たれるため、mid+1 は常に存在します。
最初の例では、mid = 2 のとき 9 > 4 なので、hi = 2 です。次に、mid = 1 のとき 5 < 9 なので、lo = 2 となり、これが山頂です。5000 個の値なら、最大 13 ステップです。
アルゴリズム
lo = 0、hi = n-1を設定します。lo < hiの間、mid = lo + (hi - lo) / 2を求め、小数部分を切り捨てます。nums[mid] < nums[mid+1]の場合、lo = mid + 1を設定します。- それ以外の場合は、
hi = midを設定します。 loを返します。
def findPeakElement(nums):
lo, hi = 0, len(nums) - 1 # the peak is always inside [lo, hi]
while lo < hi:
mid = lo + (hi - lo) // 2 # mid < hi, so mid + 1 is a valid index
if nums[mid] < nums[mid + 1]:
lo = mid + 1 # still climbing: the peak is to the right of mid
else:
hi = mid # going down: the peak is mid or to its left
return lo
落とし穴と境界ケース
- 一段階縮める際に
hi = mid - 1を設定すること。[2, 5, 9, 4, 1]では最初のmidはピークそのものであり、hi = 1にするとそれを除外してしまい、探索結果は1になります。 midを切り下げながらnums[mid-1]と比較すること。midが0になる場合があり、その場合は左隣が存在しません。hi = nとして半開区間を使うこと。その場合、midがn-1になることがあり、nums[mid+1]は範囲外を読み取ります。値が1つだけの場合は、最初からそうなります。- LuaとRでのシフトを忘れること。答えは引き続き0始まりのインデックスなので、位置
iはi-1として返します。
よくある質問3
Find Peak Element の時間計算量は何ですか？
二分探索は時間計算量が O(log n)、空間計算量が O(1) で、5000 個の値に対して最大 13 ステップです。左からの走査は O(n) です。下降箇所を見つけるまでに、すべてのペアを読み取る可能性があるためです。
ピークが複数ある場合でも、二分探索は機能しますか？
はい、隣り合う値が異なり、両端の外側の位置がすべての値より低いとみなされる限り、そうです。返されるのは1つのピークであり、必ずしも最高値ではありません。値が上昇した後、遅くとも範囲の終わりまでには下降に転じる必要があり、最初に転じた位置がピークなので、探索で残される側には常に1つのピークがあります。
ピークは常に最大値ですか？
この問題では、はい。配列は1つのピークまで上昇し、その後は下降するため、それより大きな値はほかにありません。複数のピークがあるバージョンではそうではありません。両隣より大きい値はどれもピークとみなされるからです。そのため、この探索では最大値を探すのではなく、隣り合う要素を比較します。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def findPeakElement(nums):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
nums = [2, 5, 9, 4, 1]
期待される出力
2