1004. Max Consecutive Ones III *

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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.

Code

class Solution {
    public int longestOnes(int[] nums, int k) {
        int max = 0;
        int p0 = -1;
        int start = 0;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1) {
                // 得到最长的连续的1
                max = Math.max(max, i - start + 1);
            } else {
                // 当前为0
                if (p0 == -1)
                    p0 = i;

                if (k > 0) {
                    // 用掉一个k
                    max = Math.max(max, i - start + 1);
                    k--;
                } else {
                    start = p0 + 1;
                    for (int j = p0 + 1; j < nums.length; j++) {
                        // 此时又有一个k一个用了
                        if (nums[j] == 0) {
                            p0 = j;
                            break;
                        }
                    }
                }
            }
        }

        return max;
    }
}