class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
}
};
1004. 最大连续1的个数 III
给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。
示例 1：
输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2 输出：6 解释：[1,1,1,0,0,1,1,1,1,1,1] 粗体数字从 0 翻转到 1，最长的子数组长度为 6。
示例 2：
输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3 输出：10 解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] 粗体数字从 0 翻转到 1，最长的子数组长度为 10。
提示：
1 <= nums.length <= 105nums[i] 不是 0 就是 10 <= k <= nums.length原站题解
python3 解法, 执行用时: 168 ms, 内存消耗: 15.6 MB, 提交时间: 2022-12-04 12:54:47
class Solution:
def longestOnes(self, nums: List[int], k: int) -> int:
n = len(nums)
left = lsum = rsum = 0
ans = 0
for right in range(n):
rsum += 1 - nums[right]
while lsum < rsum - k:
lsum += 1 - nums[left]
left += 1
ans = max(ans, right - left + 1)
return ans
javascript 解法, 执行用时: 72 ms, 内存消耗: 45.6 MB, 提交时间: 2022-12-04 12:54:26
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var longestOnes = function(nums, k) {
const n = nums.length;
let left = 0, lsum = 0, rsum = 0;
let ans = 0;
for (let right = 0; right < n; ++right) {
rsum += 1 - nums[right];
while (lsum < rsum - k) {
lsum += 1 - nums[left];
++left;
}
ans = Math.max(ans, right - left + 1);
}
return ans;
};
golang 解法, 执行用时: 40 ms, 内存消耗: 6.8 MB, 提交时间: 2022-12-04 12:54:13
func longestOnes(nums []int, k int) (ans int) {
var left, lsum, rsum int
for right, v := range nums {
rsum += 1 - v
for lsum < rsum-k {
lsum += 1 - nums[left]
left++
}
ans = max(ans, right-left+1)
}
return
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
golang 解法, 执行用时: 68 ms, 内存消耗: 6.8 MB, 提交时间: 2022-12-04 12:53:59
func longestOnes(nums []int, k int) (ans int) {
n := len(nums)
P := make([]int, n+1)
for i, v := range nums {
P[i+1] = P[i] + 1 - v
}
for right, v := range P {
left := sort.SearchInts(P, v-k)
ans = max(ans, right-left)
}
return
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
javascript 解法, 执行用时: 136 ms, 内存消耗: 49.6 MB, 提交时间: 2022-12-04 12:53:45
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var longestOnes = function(nums, k) {
const n = nums.length;
const P = new Array(n + 1).fill(0);
for (let i = 1; i <= n; ++i) {
P[i] = P[i - 1] + (1 - nums[i - 1]);
}
let ans = 0;
for (let right = 0; right < n; ++right) {
const left = binarySearch(P, P[right + 1] - k);
ans = Math.max(ans, right - left + 1);
}
return ans;
};
const binarySearch = (P, target) => {
let low = 0, high = P.length - 1;
while (low < high) {
const mid = Math.floor((high - low) / 2) + low;
if (P[mid] < target) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
};
python3 解法, 执行用时: 264 ms, 内存消耗: 16.4 MB, 提交时间: 2022-12-04 12:53:33
class Solution:
def longestOnes(self, nums: List[int], k: int) -> int:
n = len(nums)
P = [0]
for num in nums:
P.append(P[-1] + (1 - num))
ans = 0
for right in range(n):
left = bisect.bisect_left(P, P[right + 1] - k)
ans = max(ans, right - left + 1)
return ans
java 解法, 执行用时: 3 ms, 内存消耗: 43 MB, 提交时间: 2022-12-04 12:52:42
class Solution {
public int longestOnes(int[] nums, int k) {
int N = nums.length;
int res = 0;
int left = 0, right = 0;
int zeros = 0;
while (right < N) {
if (nums[right] == 0)
zeros ++;
while (zeros > k) {
if (nums[left++] == 0)
zeros --;
}
res = Math.max(res, right - left + 1);
right ++;
}
return res;
}
}
python3 解法, 执行用时: 172 ms, 内存消耗: 15.7 MB, 提交时间: 2022-12-04 12:51:39
class Solution:
def longestOnes(self, nums: List[int], k: int) -> int:
N = len(nums)
res = 0
left, right = 0, 0
zeros = 0
while right < N:
if nums[right] == 0:
zeros += 1
while zeros > k:
if nums[left] == 0:
zeros -= 1
left += 1
res = max(res, right - left + 1)
right += 1
return res