1493. Longest Subarray of 1's After Deleting One Element (使用 C 語言解題)

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

Solved

Medium

Topics

Companies

Hint

Given a binary array nums, you should delete one element from it.

Return the size of the longest non-empty subarray containing only 1's in the resulting array. Return 0 if there is no such subarray.

 

Example 1:

Input: nums = [1,1,0,1]
Output: 3
Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1's.

Example 2:

Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].

Example 3:

Input: nums = [1,1,1]
Output: 2
Explanation: You must delete one element.

 

Constraints:

• 1 <= nums.length <= 105
• nums[i] is either 0 or 1.

google 翻譯：

給定一個二進位陣列 nums，您應該從中刪除一個元素。
傳回結果陣列中僅包含 1 的最長非空子數組的大小。如果不存在這樣的子數組，則傳回 0。

想法一：

把 1004 的 k 改為 1，就跟題目幾乎類似了...
先用 right 把可以翻轉 0 的 k 個扣完，就是目前這時連續1的最大數量。
再加入 left +回翻轉個數，最後兩個差值就會是 1 的最大數量。

寫法一：

int longestSubarray(int* nums, int numsSize) {
    int left = 0, right = 0;
    int k = 1;
    while(right < numsSize) {
        if(nums[right++] == 0) // 移動 right
            k--;
        if(k < 0) { // k 沒了才需要移動 left
            if(nums[left++] == 0)
                k++;
        }
    }
    return right - left - 1; // 差值 -1 即為所求
}

結果一：

似乎還可以更好哦...

想法二：

用0分成左右兩邊1的長度，再相加後判斷大小

寫法二：

int longestSubarray(int* nums, int numsSize) {
    int left = 0, right = 0, i = 0;
    int max = 0;

    // 沒有 0 的陣列，直接回傳結果
    for(i=0; i<numsSize; i++) {
        if(nums[i] == 0)
            break;
    }
    if(i >= numsSize) return numsSize - 1;

    i = 0;
    while(i < numsSize) {
        if(nums[i++] == 1) { // 為1，繼續累加
            right++;
        } else { // 為0，分成左右兩邊，並相加上次的兩邊且判斷最大值
            max = fmax(max, left+right);
            left = right;
            right = 0;
        }
    }
    return  fmax(max, left+right); // 離開 while 也要判斷目前的兩邊
}

結果二：

結果還不錯哦...