LC: 487. Max Consecutive Ones II
https://leetcode.com/problems/max-consecutive-ones-ii/
487. Max Consecutive Ones II
Given a binary array nums, return the maximum number of consecutive 1's in the array if you can flip at most one 0.
Example 1:
Input: nums = [1,0,1,1,0]
Output: 4
Explanation: Flip the first zero will get the maximum number of consecutive 1s. After flipping, the maximum number of consecutive 1s is 4.Example 2:
Input: nums = [1,0,1,1,0,1]
Output: 4Constraints:
1 <= nums.length <= 105nums[i]is either0or1.
Follow up: What if the input numbers come in one by one as an infinite stream? In other words, you can't store all numbers coming from the stream as it's too large to hold in memory. Could you solve it efficiently?
The Essence:
Wenn man 0 mit 1 tauscht, verbindet man eigentlich zwei Datenblöcke, die eine bestimmte Anzahl von 1 enthalten. Diese Blöcke können natürlich auch keine 1 habe, dann ist ihre Länge 0. Wenn man das Array durchläuft, ist der Zeiger entweder innerhalb eines linken Blocks oder eines rechten Blocks in Bezug auf einen vorigen Block.
Details:
Wenn man in Durchlauf 0 begegnet, dann wird die Länge des linken Blocks zu zu der Länge des aktuellen rechten Blocks upgedatet. Wir setzen dabei die Länge des rechten Blocks zu 0 zurück. Bevor man updatet, soll man auch die Länge des verbundenen Blocks berechnen, um die Längste zu bestimmen
Solution(s): The code implementation can be found here:
Default Code:
Last updated