[Sliding Window][Medium] 1493. Longest Subarray of 1's After Deleting One Element

https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/description

Longest Subarray of 1's After Deleting One Element - LeetCode

 

Q. 1과 0으로 이루어진 nums 배열이 주어질때, 0을 하나 제거할 수 있다. 이때 구할 수 있는 최대 길이의 1로만 이루어진 sub arry의 길이를 구하라. 0이 없어도 하나는 제거 해야 한다. 

 

Solution. 위 문제와 거의 같은 문제. 다만 k==1이라 보면 되겠다. 

조금의 속도 최적화를 위해 이번에는 이전 0이 나왔던 지점을 기억하는 변수를 하나 더 둬 봤다. 

 

int longestSubarray(vector<int>& nums)
{
    int left = 0;	int left_with_0 = -1;
    int flip = 1;
    int ret = 0;
    for (int right = 0; right < nums.size(); ++right)
    {
        int cur = nums[right];
        if (cur == 0)
        {
            --flip;
            if (left_with_0 < 0)	left_with_0 = right;
        }

        if (flip < 0)
        {
            flip = 0;
            left = left_with_0 + 1;	// 이전 0의 바로 다음부터 sub array 재시작.
            left_with_0 = right;	// 새로나온 0 위치를 caching.
        }
        ret = max(ret, right - left);
    }
    return ret;
}