Last Stone Weight
石の山があり、stones[i] は石 i の重さです。各ラウンドで、最も重い石を2つ取り出してぶつけます。重さが同じなら、両方とも砕けます。異なる場合は、軽い方が砕け、重い方は2つの重さの差だけ軽くなります。
石が最大でも1つになるまでラウンドを繰り返し、その石の重さを返す lastStoneWeight という関数を書いてください。石が残っていない場合は、0 を返します。
関数
- stonesinteger-array
- 山の中の石の重さ
- 戻り値integer
- 最後に残った石の重さ。石が残っていない場合は 0
制約
1 ≤ stones.length ≤ 1041 ≤ stones[i] ≤ 1000
例
- 入力
- stones = [3, 9, 4, 6, 2]
- 出力
- 0
- 説明
9と6から3が残り、次に4と3から1が残り、次に3と2からもう一つの1が残ります。重さ1の石は互いに破壊し合うため、何も残らず、答えは0です。
- 入力
- stones = [10, 4, 1]
- 出力
- 5
- 説明
10と4から6が残り、6と1から5が残ります。石が 1 個残り、その重さは5です。
- 入力
- stones = [8]
- 出力
- 8
- 説明
- 石が1つだけではぶつける相手がいないため、その重さである
8が答えです。
提出時に隠しテスト+13件
発展問題
重さは最大で1000です。この上限を利用して、ヒープを使わずに O(n + W) 時間で処理できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
説明されているとおりにラウンドを進めましょう。各ラウンドの開始時にすばやく見つける必要があるものは何ですか？
各ラウンドでは最も重い2つの石が必要で、戻す石は山にすでにある石より軽くなることがあります。新しい値が追加された後でも常に最大値がわかるデータ構造を使えば、再度ソートせずに済みます。
すべての石を最大ヒープに入れます。2回取り出し、差が0でない場合はその差を追加し、石が1個以下になるまで繰り返します。その石を返すか、
0を返します。
解説
ルールはシミュレーションです。先へ進むための公式はないため、各ラウンドをプレイします。各ラウンドでは、変化し続ける山から最も重い石を2つ取り出す必要があります。砕かれた石は、より軽くなって戻ってくることがあるためです。毎ラウンド並べ替えれば見つけられますが、ラウンドごとに O(n log n) のコストがかかります。最大ヒープなら、最も重い石を取り出し、新しい石を O(log n) で追加できます。
各ラウンドで山を並べ替える
正しいが、最大のテストでは終わらない
考え方
ルールに文字どおり従います。石の山を並べ替えて、最も重い2つの石が末尾に来るようにし、それらを取り除きます。重さが異なる場合は、その差を戻します。石が1個または0個になるまで繰り返します。
差は並びのどこにでも入る可能性があります。最初の例では、9と6から3が残ります。これは4より軽いので、次のラウンドで新たに最も重い2つを見つける前に、もう一度並べ替えます。
各ラウンドで少なくとも1個の石を取り除くため、ラウンド数は最大でn-1回です。各ラウンドでは最大n個の石を並べ替えるので、計算量はO(n² log n)です。n = 10^4の場合、最大10^4個の数を並べ替える処理が約10^4回必要になり、リストがほぼ整列済みであることをソートが認識しても、少なくとも5 × 10^7ステップかかります。認識できない場合は、その数倍かかります。これは最大規模のテストには遅すぎますが、以下のヒープなら数十万ステップで済みます。
アルゴリズム
- 石を
pileというリストにコピーします。 - 石が1つより多く残っている間、昇順に並べ替えます。
- 最後の2つの石、
heaviestとsecondを取り出します。 - 2つの重さが異なる場合は、
heaviest - secondを山に戻します。 - 残った石を返します。山が空の場合は
0を返します。
def lastStoneWeight(stones):
pile = list(stones)
while len(pile) > 1:
pile.sort() # the two heaviest stones move to the end
heaviest = pile.pop()
second = pile.pop()
if heaviest != second:
pile.append(heaviest - second)
return pile[0] if pile else 0最大ヒープ
考え方
各ラウンドで必要なのは最大の石だけで、全体を並べ替える必要はありません。そのために最大ヒープを使います。最大値を先頭に保ち、先頭の要素の削除や値の追加には O(log n) のコストがかかります。
すべての石をヒープに入れます。各ラウンドで2回取り出し、最も重い2つを得ます。2つの値が異なる場合は、その差をヒープに戻します。ヒープが自動的に正しい位置へ移動させます。[10, 4, 1] の場合、10 と 4 を取り出して 6 を入れ、次に 6 と 1 を取り出して 5 を入れると、ヒープには 5 だけが残ります。
ラウンドは最大でも n-1 回で、各ラウンドでは2回の取り出しと最大1回の追加を行うため、時間計算量は O(n log n)、ヒープが使う領域は O(n) です。ヒープが標準で用意されている言語もあります。Python の heapq は最小ヒープなので、重みの符号を反転して格納します。Java には PriorityQueue、C++ には priority_queue、Go には container/heap、Rust には BinaryHeap、PHP には SplMaxHeap があります。それ以外の言語では、解法内で配列を使ったヒープを実装します。インデックス i の親は (i-1)/2 にあり、新しい値は親より大きい間、上へ移動します。
アルゴリズム
- すべての石を最大ヒープに入れます。
- ヒープに石が1個より多くある間、最も重い石を取り出し、次に2番目に重い石を取り出します。
- 重さが異なる場合は、
heaviest - secondを追加します。 - ヒープが空の場合は
0を返し、そうでなければヒープの先頭を返します。
import heapq
def lastStoneWeight(stones):
# heapq is a min-heap, so store negated weights: the smallest entry is the heaviest stone.
heap = [-w for w in stones]
heapq.heapify(heap)
while len(heap) > 1:
heaviest = -heapq.heappop(heap)
second = -heapq.heappop(heap)
if heaviest != second:
heapq.heappush(heap, -(heaviest - second))
return -heap[0] if heap else 0
落とし穴と境界ケース
シミュレーションは短いため、バグは端やヒープそのものに潜んでいます。
- 空の山の先頭を返す。最後の2つの石の重さが同じなら、何も残らず、答えは
0です。 - 誤って最小ヒープを使う。Python の
heapqと Java のデフォルトのPriorityQueueは最小の値を取り出すため、重さを負の値にするか、逆順の比較関数を渡してください。 - 符号を戻し忘れる。
heapqでは、取り出した値はどちらも負の値なので、プッシュする差は-(heaviest - second)です。 - 最初に一度だけ並べ替えて、リストを順にたどる。2つの石の差は、まだ取り出していない石より軽くなることがあるため、最初のラウンドの後は固定された順序が古くなります。
よくある質問4
Last Stone Weight の時間計算量はどれくらいですか？
最大ヒープを使うと、ヒープの構築と、最大 n-1 ラウンドの「2回のポップと1回のプッシュ」の実行に、時間計算量 O(n log n)、空間計算量 O(n) がかかります。代わりに各ラウンドで山全体をソートすると、O(n² log n) かかります。
Last Stone Weight にヒープを使う理由
各ラウンドでは、ラウンドごとに変化するコレクションから、最も大きい値を2つ求めます。ヒープを使うと「最大値は何か」という問いに答えられ、コレクション全体をソートした状態に保たずに、新しい値を O(log n) で追加できます。シミュレーションで繰り返される処理そのものです。
Last Stone Weightはヒープを使わずに解けますか？
はい、重さが小さいためです。重さが1から1000までの各石の個数を数え、最も重い重さから順に見ていきます。同じ重さの石は2つずつ相殺され、新しい石はそれを作るために使った最も重い石より常に軽いため、見ていく重さは下がる一方です。最大の重さをWとすると、これはO(n + W)時間で実行できます。
同じ重さの石を砕く順序によって、答えは変わりますか？
いいえ。最も重い重さの石が複数ある場合、どちらを選んでも選んだ2つの石の重さは同じなので、ラウンド後の山に残る石の重さも同じです。答えは重さだけに依存するため、正しい解法はどれも同じ数を返します。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def lastStoneWeight(stones):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
stones = [3, 9, 4, 6, 2]
期待値
0