Max Consecutive Ones
各値が0または1である配列numsが与えられます。連続区間とは、その間に0を挟まず隣り合って並ぶ1の集まりです。最も長い連続区間の長さを返してください。配列に1が一つも含まれない場合は、0を返してください。
関数
- numsinteger-array
- 0と1の配列
- 戻り値integer
- 連続する1の最長の並びの長さ
制約
1 ≤ nums.length ≤ 2 × 104- それぞれの
nums[i]は0または1です。
例
- 入力
- nums = [1, 1, 0, 1, 1, 1, 0, 1]
- 出力
- 3
- 説明
- 1の連続部分は3つあります。インデックス
0から1まで（長さ2）、3から5まで（長さ3）、そしてインデックス7のみ（長さ1）です。最も長いものの長さは3です。
- 入力
- nums = [0, 1, 0, 1, 1]
- 出力
- 2
- 説明
- 連続部分は、インデックス
1にある単独の1と、インデックス3と4にあるペアです。長さ2のペアが最長です。
- 入力
- nums = [0, 0, 0]
- 出力
- 0
- 説明
- どこにも 1 がないため、連続した並びはなく、答えは
0です。
提出時に隠しテスト+14件
発展問題
最大でk個の0を1に反転できるとしたらどうでしょうか？1の最長連続区間はどれくらい長くなり、1回の走査で見つけることができるでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
0が現れた瞬間に、1の連続は終わります。すでに通過した値について、何を覚えておく必要がありますか？現在のインデックスで終わる連続部分の長さだけが重要です。1なら長さが1増え、0なら0に戻ります。
2つの数値、つまり現在の連続区間の長さと、これまでの最長の長さを使って、配列を1回走査します。各1の後で現在の連続区間を伸ばし、最長の長さと比較します。各0の後で現在の連続区間をリセットします。
解説
0が現れた瞬間に連続区間は終わるため、各インデックスで知る必要があるのは、そこで終わる連続区間の長さだけです。各インデックスで最初から数えると、同じ作業を何度も繰り返すことになります。1で増え、0でリセットされるカウンターを1つ使えば、1回の走査で答えが得られます。
すべてのインデックスから順方向に数える
正しいが、最大のテストでは終わらない
考え方
すべての連続区間には開始位置があります。そこで、各インデックスを開始位置として試し、1が続く間は前方へ進みます。歩数が、その位置から始まる連続区間の長さです。すべての開始位置で得られた数のうち最大のものが答えです。[1, 1, 0, 1, 1, 1, 0, 1]の場合、インデックス3から始めると、インデックス6の0に出会うまでに3つの1を通るので、結果は3です。
最長の連続区間は試す開始位置のいずれかから始まり、その最初のインデックスから進むことで、その長さを正確に測れるため、この答えは正しいです。
計算コストは重複部分に隠れています。n個の1が並ぶ配列では、インデックス0から始めるとn歩、次の位置から始めるとn-1歩進み、以下同様に続くため、合計で約n² / 2歩になります。n = 2 × 10^4の場合、これは2 × 10^8歩になり、実行速度の遅い言語では制限時間内に収めるには多すぎます。
アルゴリズム
best = 0を設定します。- 各インデックス
startについて、length = 0を設定します。 start + lengthが配列内にあり、nums[start + length]が1である間、lengthに1を加えます。bestとlengthの大きい方を保持します。bestを返します。
def findMaxConsecutiveOnes(nums):
n = len(nums)
best = 0
for start in range(n):
length = 0
while start + length < n and nums[start + length] == 1:
length += 1
best = max(best, length)
return best実行中のカウントを使った1回のパス
考え方
配列を1回走査し、現在のインデックスで終わる1の連続数を表すcurrentを保持します。1が出るとその連続が続くため、currentは1増えます。0が出ると連続が終わるため、currentは0に戻ります。1が出るたびに、currentとbestを比較します。
[1, 1, 0, 1, 1, 1, 0, 1]では、currentは1、2、0、1、2、3、0、1となり、その最大値は3です。各連続区間は最後のインデックスで測定され、その時点でcurrentは連続区間全体の長さと等しくなるため、得られた最大値が最長の連続区間の長さです。
各値は1回だけ読み取るため、時間計算量はO(n)です。また、必要なメモリは整数2つだけです。
アルゴリズム
best = 0とcurrent = 0を設定します。numsの各値について、値が1ならcurrentに 1 を加え、bestとcurrentの大きい方を保持します。- 値が
0なら、current = 0を設定します。 bestを返します。
def findMaxConsecutiveOnes(nums):
best = 0
current = 0
for x in nums:
if x == 1:
current += 1
best = max(best, current)
else:
# A 0 breaks the run.
current = 0
return best
落とし穴と境界ケース
1回走査版は短いため、バグは答えを更新する箇所から発生します。
0に遭遇したときだけbestを更新する。配列の末尾まで続く区間（[0, 1, 1]など）が記録されません。1が続くたびに更新するか、ループの後でもう一度比較してください。0でcurrentをリセットし忘れると、別々の区間の1が合算され、[1, 1, 0, 1, 1]に対して4を返します。bestを1またはnums[0]で初期化する。0だけの配列は0を返さなければなりません。- LuaとRでは配列のインデックスが
1から始まるため、前方向への走査では< nではなくstart + length ≤ nをチェックします。
よくある質問4
Max Consecutive Ones の時間計算量は何ですか？
1回走査の解法は、各値を正確に1回読み取るため、時間計算量は O(n) です。追加の空間計算量は O(1) です。現在の連続部分用と最大値用のカウンターを1つずつ使います。すべてが1の配列で、各インデックスでカウントを再開すると、時間計算量は O(n²) になります。
カウンターが1ではなく0にリセットされるのはなぜですか？
カウンターは、現在のインデックスで終わる連続部分の長さを保持します。現在の値が 0 の場合、そこで終わる1の連続部分はないため、その長さは 0 です。次の1が来るとカウンターは 1 になり、新しい連続部分の長さとして正しい値になります。
これはスライディングウィンドウの問題ですか？
これを1つのものとして見ることができます。ウィンドウは現在の連続部分を保持し、値が進むたびに右端が移動し、0が現れると左端がその先まで移動します。ここではウィンドウを少しずつ縮める必要がないため、2つの端の代わりに1つのカウンターで済みます。ウィンドウの見方が役立つのは、最大k個の0を1に反転できる、より難しいバージョンです。
0を1つ反転できる場合、連続する1の数をどのように数えますか？
2つのカウンターを保持します。ここで終わる、反転なしの連続区間の長さと、すでに1回反転した連続区間の長さです。1の場合は、どちらも1増やします。0の場合は、反転済みのカウントを通常のカウントに1を足した値にし、通常のカウントを0にリセットします。答えは、1回の走査で見つけた反転済みカウントの最大値です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def findMaxConsecutiveOnes(nums):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
nums = [1, 1, 0, 1, 1, 1, 0, 1]
期待値
3