牛客网真题-80-最长全1串-MT美团45

本题折磨了很久，写了三种方法

• queue入队，保证队列中刚好k个-1：60%，写的太乱就不放了
• 把连续的0和1合并，组成一个正负相间的数组，见注释部分的代码：80%
• 双指针：参考评论区大佬：未注释部分

  package org.niuke.solution80;
  

import java.util.*;

public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
int[] ints = new int[n];
for(int i = 0; i < n; i++){
ints[i] = scanner.nextInt();
}
int start = 0, cnt = 0, len = 0;
for(int i = 0; i < ints.length; i++){
if(ints[i] == 0){
cnt++;
}
if(cnt > k){
len = Math.max(len, i - start);
while (ints[start] == 1) {
start++;
}
start++;
cnt--;
}
// System.out.println(i + " cnt " + cnt + " start:" + start + " len:" + len);
}
len = Math.max(len, n - start);
System.out.println(len);

    //        int l = 0, r = 0, cnt = 0;
    //        Deque<Integer> deque = new LinkedList<>();
    //
    //        for(int i = 0; i < n; i++){
    //            int temp = ints[i];
    //            if(i == 0){
    //                deque.addLast(temp == 0 ? -1 : 1);
    //            }else{
    //                int last = deque.pollLast();
    //                if(last < 0 && temp == 0){
    //                    deque.addLast(last - 1);
    //                }else if(last > 0 && temp == 1){
    //                    deque.addLast(last + 1);
    //                }else{
    //                    deque.addLast(last);
    //                    deque.addLast(temp == 0 ? -1 : 1);
    //                }
    //            }
    //        }
    //        int[] res = new int[deque.size()];
    //        for(int i = 0; i < res.length; i++){
    //            res[i] = deque.pollFirst();
    //        }
    //
    //        int len = 0;
    //        for(int i = 0; i < res.length; i++){
    //            int lenTemp = 0, zero = k;
    //            for(int j = i; j < res.length; j++){
    //                if(zero + res[j] < 0){
    //                    len = Math.max(len, lenTemp + zero);
    //                    break;
    //                }else{
    //                    zero += Math.min(res[j], 0);
    //                    lenTemp += Math.abs(res[j]);
    //                }
    //            }
    //
    //        }
    //        System.out.println(len);
}

}

```