1004. Max Consecutive Ones III - Medium

前往題目

思路

• 看到subarray基本上是用sliding window
• 看到可以翻轉k個，基本上可以用dp

1. sliding window
2. 如果遇到1，就紀錄長度
3. 如果遇到0，就紀錄當前幾個0，超過k的話把左邊指針右移直到0的個數小於等於k，然後再紀錄一下長度

Code

官神影片同時講了dp和sliding window，dp在這題不太可行是因為需要用到二維陣列，這樣nums.length如果是$10^5$，就需要$10^5 * 10^5$的陣列，空間上太不划算。使用sliding window只需要O(1)空間以及O(n)時間

class Solution {
    public int longestOnes(int[] nums, int k) {
        int res = 0;
        int i = 0;
        int count = 0;
        // 右指針持續向右
        for (int j = 0; j < nums.length; ++j) {
            // 遇到1
            if (nums[j] == 1) {
                res = Math.max(res, j - i + 1);
            } else {  // 遇到0
                ++count;
                // 移動左指針直到count小於等於k
                while (count > k) {
                    // 刪掉0的話count也要減1
                    if (nums[i] == 0) {
                        --count;
                    }
                    ++i;
                }
                res = Math.max(res, j - i + 1);
            }
        }
        return res;
    }
}