1. 題目鏈接

2. 分析

最多可以將K個值從0變成1,因此滑動窗口的限制條件: 0的數量(zeros)小于K,算法過程如下

1. 有一個滑動窗口(slipper),每次都會從A中讀入一個數
2. 當讀入的數為0時,zeros++
3. 當zeros的數量大于K時,會取出slipper首部的元素,當取值為0時zeros--
   總體代碼如下:

var longestOnes = function (A, K) {let slipper = [];let len = A.length;let res = 0;let zeros = 0;for (let right = 0; right < len; right++) {slipper.push(A[right]);if (A[right] == 0) {zeros++;}while (zeros > K) {if (slipper.shift() == 0) {zeros--;}}res = Math.max(res, slipper.length);}return res;
};

3. 改進

上述算法效率并不高:

1. 數值沒有必要每次入棧,只需要使用left、right來界定范圍即可

使用left和right來界定滑動窗口中的值
改進后的算法如下:

var longestOnes = function (A, K) {let len = A.length;let res = 0;let zeros = 0;let left = 0;for (let right = 0; right < len; right++) {if (A[right] == 0) {zeros++;}while (zeros > K) {if (A[left++] == 0) {zeros--;}}res = Math.max(res, right - left + 1);}return res;
};

效率大大提高.