問題
サイコロシミュレーターは、6面のサイコロを振った結果をすべてリストに記録します。ここでいう「連続」とは、同じ目が続けて出たひとまとまりのことで、1回だけ出た目も長さ1の連続です。最長の連続を見つけてください。最長の長さの連続が複数あれば、最初に始まるものを答えます。
longest_run_of_rolls(rolls) を実装してください。
入力
rolls: 出た順に並べた目。それぞれ1から6です。
出力
最長の連続が始まる0始まりの添字と、その長さを [start, length] として返してください。リストが空なら [-1, 0] を返します。
制約
0 ≤ 振った回数 ≤ 10,000
1 ≤ 目 ≤ 6
例
例 1
入力:
rolls = [1, 4, 4, 2, 6, 6, 6, 3]
期待される出力:
expected = [4, 3]
入力:
std::vector<long long> rolls = {1, 4, 4, 2, 6, 6, 6, 3};
期待される出力:
std::vector<long long> expected = {4, 3};
入力:
long[] rolls = new long[] {1, 4, 4, 2, 6, 6, 6, 3};
期待される出力:
long[] expected = new long[] {4, 3};
解説
添字4から始まる3つの6が、2つの4より長いので [4, 3] です。
例 2
入力:
rolls = [5, 5, 2, 2, 3]
期待される出力:
expected = [0, 2]
入力:
std::vector<long long> rolls = {5, 5, 2, 2, 3};
期待される出力:
std::vector<long long> expected = {0, 2};
入力:
long[] rolls = new long[] {5, 5, 2, 2, 3};
期待される出力:
long[] expected = new long[] {0, 2};
解説
どちらのペアも長さ2で、5の方が添字0から先に始まるので [0, 2] です。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
現在の連続がどこから始まったかを覚えておきましょう。
ヒント 2
値が変わったとき(またはリストが終わったとき)、終わった連続をそれまでの最良のものと比べます。
ヒント 3
新しい連続のほうが真に長いときだけ、最良のものを置き換えます。
目安の計算量
時間 O(n)、追加メモリ O(1)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。