Next Greater Element I
相異なる整数からなる2つの配列 nums1 と nums2 が与えられます。nums1 の各値は nums2 にも含まれています。値 x の次に大きい要素とは、nums2 で x より右にある値のうち、x より大きい最初の値です。そのような値がない場合は -1 とします。
nums1 の各値に対する次に大きい要素を、nums1 の順序で格納した配列を返してください。
関数
- nums1integer-array
- 答えとなる値は、すべてnums2にあります
- nums2integer-array
- 各値の右側を調べる配列
- 戻り値integer-array
- nums1 の各値に対する次に大きい要素、または -1 を、nums1 の順序で
制約
1 ≤ nums1.length ≤ nums2.length ≤ 1040 ≤ nums1[i], nums2[i] ≤ 104-
nums1のすべての値は互いに異なり、nums2のすべての値も互いに異なります。 - nums1 のすべての値は nums2 に含まれています。
例
- 入力
- nums1 = [3, 8, 1]nums2 = [1, 6, 3, 8, 2]
- 出力
- [8, -1, 6]
- 説明
nums2の 3 の後には 8 と 2 が続き、3 より大きい最初の値は 8 です。8 の後に続くのは 2 だけなので、8 には -1 が割り当てられます。1 のすぐ後の値は 6 で、これはすでにより大きい値です。
- 入力
- nums1 = [5, 2]nums2 = [2, 9, 5, 4]
- 出力
- [-1, 9]
- 説明
- 5の後に続くのは4だけで、4のほうが小さいため、5には-1が割り当てられます。2の直後の値は9です。答えは
nums2の順序ではなく、nums1の順序に従います。
- 入力
- nums1 = [10, 0]nums2 = [0, 10, 11]
- 出力
- [11, 10]
- 説明
- 10の後の最初の値は11です。0の後の最初の値は10で、こちらのほうが大きいため、後からさらに大きな11が来るにもかかわらず、0には10が割り当てられます。
提出時に隠しテスト+14件
発展問題
nums2の各位置について、同じ1回の走査で、その次に大きい要素が右側に何ステップ離れているかを返せますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
nums1の各値について右側を走査すると、値ごとに最大 10^4 ステップかかることがあります。答えはnums2のみに依存します。nums2のすべての値について、次に大きい要素を 1 回の走査で求めてから、nums1の値を調べることはできますか？nums2を左から右へたどり、まだより大きな値に出会っていない値を保持します。新しい値が来たら、それより小さい待機中のすべての値に対する答えになります。待機中の値は常に減少する並びになるため、小さい値がスタックの上に置かれます。nums2の各値について、スタックの先頭がその値より小さい間、先頭の値を取り出し、現在の値をハッシュマップにその答えとして記録します。その後、現在の値をプッシュします。最後に、マップを使ってnums1の各値に答えます。一度も取り出されなかった値には-1を返します。
解説
1つの値に対する答えは、その右側を走査すれば見つかりますが、nums1のすべての値について走査すると、最大でnums1.length × nums2.lengthステップかかります。答えはnums2だけに依存するため、単調スタックを使ってnums2のすべての値の次に大きい要素を一度に見つけ、ハッシュマップに保持すれば、検索によってnums1の答えを求められます。
各値を見つけて右方向に走査する
正しいが、最大のテストでは終わらない
考え方
定義どおりに行います。nums1の値xについて、xに到達するまでnums2を順にたどります。その後もたどり続け、xより大きい最初の値で止まります。そのような値が見つからないまま末尾に到達した場合、答えは-1です。
この方法が正しいのは、走査がxの右側にある値を順番に調べるため、最初に見つかった、より大きい値が、そこにある最初のより大きい値だからです。
答えが遠くにある場合や、答えが見つからない場合は処理が遅くなります。nums2が単調減少している場合、走査しても大きい値は見つからず、nums1の各値について末尾までたどることになります。nums1にm個、nums2にn個の値がある場合、最大でm × nステップになります。両方の配列に10^4個の値がある場合は10^8ステップです。また、各走査では、前の走査ですでに調べた範囲も繰り返し調べます。
アルゴリズム
nums1の各値xをループ処理します。nums2[j]がxと等しくなるインデックスjを見つけます。j+1からnums2を走査し、xより大きい最初の値で停止します。- その値を追加します。走査が末尾に達した場合は -1 を追加します。
- 集めた答えを返します。
def nextGreaterElement(nums1, nums2):
result = []
for x in nums1:
j = 0
while nums2[j] != x:
j += 1
answer = -1
for k in range(j + 1, len(nums2)):
if nums2[k] > x:
answer = nums2[k]
break
result.append(answer)
return result単調スタックとハッシュマップ
考え方
質問の考え方を逆にしてみましょう。それぞれの値について、その後に何が来るかを尋ねる代わりに、nums2を1回走査し、新しい値が、それより小さい先行の値に答えを与えるようにします。まだ答えがない値をスタックに保持します。値が現れたら、スタックの先頭からそれより小さい値をすべて取り出します。新しい値はそれらの右側にある最初の大きい値なので、それらの答えになります。次に、新しい値をプッシュします。この値自身は、まだ答えを待っているからです。
nums2 = [1, 6, 3, 8, 2]を順に見ていきましょう。1をプッシュします。次に6が現れて1を上回るので、1の対応値は6です。6をプッシュします。次に3が現れますが、6を上回らないため、スタックの一番上にプッシュされます。スタックは[6, 3]です。次に8が3と6を取り出すので、どちらの対応値も8です。8をプッシュします。最後に2をプッシュします。スタックは[8, 2]となり、この2つには答えがありません。nums1 = [3, 8, 1]の場合、対応付けから[8, -1, 6]が得られます。
スタックは常に、底から頂上に向かって減少しています。値がプッシュされるのは、その上にある小さい値がすべて取り出された後だからです。そのため、確認する必要があるのは常に頂上だけです。最初の大きい値が現れた時点で、その値はスタックから取り出されるため、記録する答えは最大の値ではなく、最初に現れた値です。
nums2の各値は1回プッシュされ、取り出されるのは最大1回なので、走査全体で内側のループが行うポップは合計で最大でもn回です。m回の検索を含めると、時間計算量はO(n + m)です。2つの配列を結び付けるのがマップです。値は重複しないため、nums1とnums2で異なる位置にあっても、値を安全なキーとして使えます。CとRの解法では、値をインデックスとする10^4+1個の要素を持つ配列をマップとして使用します。これは、値が10^4を超えないため機能します。
アルゴリズム
- 空のマップと空のスタックを作成します。
nums2の各値について、スタックの先頭からそれより小さい値をすべて取り出し、現在の値に対応付けます。- 現在の値をスタックにプッシュします。
nums1の各値について、対応する答えを返します。答えがない場合は-1を返します。
def nextGreaterElement(nums1, nums2):
next_greater = {}
stack = [] # values still waiting for a greater one, decreasing from bottom to top
for value in nums2:
# value is the first greater value to the right of every smaller value on the stack.
while stack and stack[-1] < value:
next_greater[stack.pop()] = value
stack.append(value)
# Whatever is still on the stack has no greater value to its right.
return [next_greater.get(x, -1) for x in nums1]
落とし穴と境界ケース
スタック自体のコードは短く、間違いは何を記録するか、どこを見るかにあります。
- 右側にある最も大きい値を記録し、最初に現れるより大きい値を記録しない。
nums2 = [3, 5, 1, 2, 4, 9, 0]では、1に対する答えは9ではなく2です。 nums2の順序で答えを返したり、nums2のすべての値に対して答えを返したりする。結果には、nums1の各値に対応する項目が、その順序で1つずつ含まれます。- 値ではなくインデックスを返す。問題で求められているのは、より大きい値そのものです。
nums1で値があるインデックスを使ってnums2を参照する。同じ値でも2つの配列では位置が異なるため、値を使って見つけます。そのためのものがマップです。- 最後にスタックに残った値を忘れる。それらの値より大きい値は見つからなかったので、答えは-1です。デフォルト値を指定しないマップ検索では、失敗するか何も返されません。
- 左側を調べたり、
nums2の先頭に戻ったりする。右側の値だけが対象で、配列は循環しません。
よくある質問4
Next Greater Element I の時間計算量は何ですか？
単調スタックを使う解法の実行時間は O(n + m) です。ここで、n は nums2 の長さ、m は nums1 の長さです。nums2 の各値はプッシュとポップがそれぞれ最大1回で、nums1 の各値について行うのはマップの検索1回です。マップとスタックは O(n) の領域を使用します。各値から右方向に走査する方法では、実行時間は O(n·m) です。
単調スタックとは何ですか？
これは、値が下から上へと並べられたスタックで、ここでは降順です。新しい値をプッシュする前に、順序を崩す値をすべてポップします。処理が行われるのはこのポップのときです。ポップされた各値は、右側で最初に見つかる自分より大きな値を見つけたことになります。これにより、次に大きい値、次に小さい値などを求める問題を線形時間で解けます。
Next Greater Element I でハッシュマップが必要なのはなぜですか？
スタックの走査では、値がスタックから取り出される順に、nums2の値をキーとして答えが得られます。出力はnums1の順序に従う必要がありますが、同じ値は別の位置にあります。すべての値が異なるため、値から答えへのマップを使えば、各値を定数時間で検索して2つの配列を対応付けられます。
nums2 が循環配列の場合、何が変わりますか？
その後、より大きな値の探索を配列の先頭から続けられます。インデックス i % n を使って、i を0から2n-1まで変化させながら、同じスタック走査を配列に対して2回行い、値をプッシュするのは1回目の走査中だけにします。2回の走査の後もスタックに残っている値は、どこにもより大きな値がないため、その答えは-1です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def nextGreaterElement(nums1, nums2):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
nums1 = [3, 8, 1] nums2 = [1, 6, 3, 8, 2]
期待値
[8, -1, 6]