1.題目
給定一個由若干 0 和 1 組成的陣列 A，我們最多可以將 K 個值從 0 變成 1 ，
回傳僅包含 1 的最長（連續）子陣列的長度，
示例 1：
輸入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
輸出：6
解釋：
[1,1,1,0,0,1,1,1,1,1,1]
粗體數字從 0 翻轉到 1，最長的子陣列長度為 6，
示例 2：
輸入：A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
輸出：10
解釋：
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗體數字從 0 翻轉到 1，最長的子陣列長度為 10，
提示：
1 <= A.length <= 20000
0 <= K <= A.length
A[i] 為 0 或 1
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/max-consecutive-ones-iii
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
2.雙指標解法，時間復雜度O(n)
這個是我自己的解法，因為原來做過類似的，直接就想到了這個方法，具體詳情可以看我之前的博客，地址在這里，
2.1 原理
我們設定兩個指標，左指標和右指標，先讓右指標移動，每經過一次0，我們就讓記錄值k - 1，一旦k == 0 時，就代表可替換的次數用完了，right - left 就是我們要的長度，那么后續的數該怎么辦呢，這時候就要輪到我們左指標了，右指標繼續移動，一旦k < 0，左指標開始移動，如果左邊移過去的元素是0，我們就要讓k++（此時我們的范圍不包括這個0，所以可替換次數要恢復），這樣不管如何，我們right - left 記錄的始終是最大的長度，在前面的博客中，也是利用的這個思路，主要是弄懂為什么right - left 是最大長度，
2.2 代碼
int longestOnes(vector<int>& A, int K) {
int left = 0, right = 0;
int k = K;
while(right < A.size()) {
if((A[right++] == 0))
k--;
if(k < 0) {
if(A[left] == 0)
k++;
left++;
}
}
return right - left;
}
3.官方解法總思路（4，5共同的思路部分）
來源于這里，
前綴和：前綴和是一個陣列的某項下標之前(包括此項元素)的所有陣列元素的和，
具體關于前綴和的可以看這里，
我們可以轉換一下題意，其實是讓我們尋找一個包含K個0元素的最大子陣列，我們將原陣列的0 和 1，變成 1 和 0，這樣我們就可以統計出哪個區段有多少個零元素，然后開辟一個陣列存盤前綴和，讓右側減去左側的前一項，就是這個區段具有的0元素的個數，
4.二分查找法,時間復雜度O(nlogn)
4.1 原理
我們知道，我們得到的前綴和陣列一定是遞增的，因為陣列只包含0 和 1，這樣我們就可以利用二分法來找到符合我們要求的位置，我們讓right從左端開始，在每一次回圈中進行二分查找，查找到left的位置，然后再與最大的長度比較，決定是否取代之前的最大長度，
4.2 代碼
class Solution {
public:
int longestOnes(vector<int>& A, int K) {
int n = A.size();
vector<int> P(n + 1);
for (int i = 1; i <= n; ++i) {
P[i] = P[i - 1] + (1 - A[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;
}
};
作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/max-consecutive-ones-iii/solution/zui-da-lian-xu-1de-ge-shu-iii-by-leetcod-hw12/
來源：力扣（LeetCode）
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，
5.滑動視窗，時間復雜度O(n)
5.1 原理
我們知道前綴和是遞增的，我們設定兩個指標，左指標和右指標，先讓右指標移動，我們無需再開辟陣列來記錄此時的前綴和值，我們只需要利用left和right兩個下標再根據lsum和rsum這兩個值來記錄前綴和值，一旦不符合公式（根據題意推出來的公式），就讓左指標開始移動，即視窗縮小，直到縮到符合要求為止，再與我們記錄的最大長度去比較即可，
5.2 代碼
class Solution {
public:
int longestOnes(vector<int>& A, int K) {
int n = A.size();
int left = 0, lsum = 0, rsum = 0;
int ans = 0;
for (int right = 0; right < n; ++right) {
rsum += 1 - A[right];
while (lsum < rsum - K) {
lsum += 1 - A[left];
++left;
}
ans = max(ans, right - left + 1);
}
return ans;
}
};
作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/max-consecutive-ones-iii/solution/zui-da-lian-xu-1de-ge-shu-iii-by-leetcod-hw12/
來源：力扣（LeetCode）
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/261293.html
標籤：其他
下一篇：我在春晚現場護航直播