本文主要是介绍LeetCode75——Day16，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文章目录
- 一、题目
- 二、题解
一、题目
1004. Max Consecutive Ones III
Given a binary array nums and an integer k, return the maximum number of consecutive 1’s in the array if you can flip at most k 0’s.
Example 1:
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: [1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
Example 2:
Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
Output: 10
Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
Constraints:
1 <= nums.length <= 105
nums[i] is either 0 or 1.
0 <= k <= nums.length
二、题解
滑动窗口+前缀和
class Solution {
public:int longestOnes(vector<int>& nums, int k) {int n = nums.size();vector<int> P(n + 1);for (int i = 1; i <= n; ++i) {P[i] = P[i - 1] + (1 - nums[i - 1]);}int ans = 0;for (int right = 0; right < n; ++right) {int left = lower_bound(P.begin(), P.end(), P[right + 1] - k) - P.begin();ans = max(ans, right - left + 1);}return ans;}
};
这篇关于LeetCode75——Day16的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
