1493. Longest Subarray of 1's After Deleting One Element

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        // the same with 1004. Max Consecutive Ones III
        int ret= 0;
        int l=0, r=0, n=nums.size();
        int window =0;
        int del=1;
        while(r<n)
        {
            int cur = nums[r++];
            if(cur == 0){
                if(del>=0){
                    del--;
                }
            }
            else window++;
            while( del<0)
            {
                int prev = nums[l++];
                if(prev==0) del++;
                else window--;
            }
            ret = max(ret, window - del); // - del ,  must delete one element.
             
        }
        return ret;
        
    }
};

analysis

  • time complexity O(n)
  • space complexity O()`