Max Consecutive Ones
すべての値が0または1である配列numsが与えられます。ランとは、間に0がなく、隣り合って並んだ1の連続部分です。最長のランの長さを返してください。配列に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です。
発展問題
最大 k 個のゼロを 1 に反転できるとしたらどうでしょうか？最長の連続部分はいくつまで長くなり、一度の走査でそれを見つけられるでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
0が現れた瞬間に、1が連続する状態は終わります。すでに通過した値について、何を覚えておく必要がありますか？現在のインデックスで終わる連続区間の長さだけが重要です。1なら長さが1増え、0なら0に戻ります。
2つの数値を使って配列を1回走査します。現在の連続区間の長さと、これまでの最長の長さです。1の後は現在の連続区間を伸ばして最長の長さと比較し、0の後は現在の連続区間をリセットします。
解説
0が現れた瞬間に連続区間は終わるので、各インデックスでは、そこを末尾とする連続区間の長さだけを求めれば十分です。1で増え、0でリセットされるカウンターを1つ使えば、1回の走査で最長の連続区間を見つけられます。
すべてのインデックスから順方向に数える
正しいが、最大のテストでは終わらない
考え方
各インデックスを開始位置として試し、1が続く間前方へ進みます。ステップ数は、そこから始まる連続区間の長さです。最長の連続区間はこれらのインデックスのいずれかから始まるため、最も大きい数が答えです。
走査は重複します。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の並びの長さをcurrentに保持します。1が続くとその並びは1つ長くなり、0が現れると並びが終わるため、currentは0になります。各並びの長さは最後のインデックスで測定され、そこではcurrentが並び全体の長さと等しくなるため、currentが取り得る最大値が答えです。
[1, 1, 0, 1, 1, 1, 0, 1]では、currentの値は1、2、0、1、2、3、0、1となり、最大値は3です。
アルゴリズム
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
落とし穴と境界ケース
0に出会ったときだけbestを更新すること。[0, 1, 1]のように最後まで続く連続部分列は記録されません。各1の後に更新するか、ループの後にもう一度比較してください。0のときにcurrentをリセットしないこと。別々の連続部分列が合算され、[1, 1, 0, 1, 1]は4を返します。bestを1またはnums[0]で初期化すること。[0, 0, 0]は0を返す必要があります。- 配列のインデックスが1から始まるLuaとRでは、前方への走査の上限に
≤ nではなく< nを使うこと。最後の値が読み取られず、[0, 1]は0を返します。
よくある質問3
Max Consecutive Ones の時間計算量はどれくらいですか？
1回の走査で解く方法は、各値を1回ずつ読み取るため、時間計算量は O(n) です。また、追加の領域は O(1) で、現在の連続部分用のカウンターと最長の連続部分用のカウンターを1つずつ使います。すべてが1の配列で各インデックスから数え直すと、O(n²) かかります。
カウンターが1ではなく0にリセットされるのはなぜですか？
カウンターは、現在のインデックスで終わる連続部分の長さを保持します。そこにある値が 0 のとき、そこで終わる1の連続部分はないため、長さは 0 です。次の1によって値は 1 になり、新しい連続部分の長さを表します。
最大連続1はスライディングウィンドウ問題ですか？
1つのものとして見ることができます。ウィンドウには現在の連続部分が保持され、その右端は値ごとに移動し、0が左端をその位置より先へ移動させます。ウィンドウは段階的に縮むことがないため、2つの端の代わりに1つのカウンターで済みます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def findMaxConsecutiveOnes(nums):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
nums = [1, 1, 0, 1, 1, 1, 0, 1]
期待される出力
3