【牛客编程巅峰赛S1第9场】牛牛的木板

题目

给定一个长度为 的数组 ，其元素只有 0 和 1。
最多可以将数组中 个元素从 0 改为 1。
问：更改后，只包含元素 1 的所有子数组中，最长的子数组长度。

解题思路

尺取法

使用双指针来确定一个移动窗口 。

1. 如果窗口内 0 的个数小于等于 ，则将 右移，扩大窗口，并更新最大长度 ，直至 0 的个数大于 。
2. 如果窗口内 0 的个数超过了 ，则将 右移，直至窗口内 0 的个数小于等于 ，继续步骤 1，直到遍历完数组中的所有元素。

C++代码

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @param a int整型vector 
     * @return int整型
     */
    int solve(int n, int m, vector<int>& a) {
        // write code here
        int ans = 0;
        int b = 0;
        int left = 0;
        int right = 0;
        while(right < n){
            if(a[right]==0){
                ++b;
                while(b>m){
                    if(a[left]==0)
                        --b;
                    ++left;
                }
            }
            ans = max(ans, right-left+1);
            ++right;
        }
        return ans;
    }
};