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

Description

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.

Constraints:

• 1 <= nums.length <= 10^5
• nums[i] is either 0 or 1.

給一個二元陣列 nums，你必須刪除裡面其中一個元素。
回傳最長只包含 1 的非空子陣列。回傳 0 如果不存在這種子陣列。

限制：

• 1 <= nums.length <= 10^5
• nums[i] 只會是 0 或是 1。

Example:

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.

Solution

• 先將原陣列換一個方式重新表達
  • 改為紀錄目前 1 連續出現的次數
  • 0 代表間隔，將 1 的計數重置
  • 例如 [0,1,1,1,0,1,1,0,1] 改為 [0, 3, 2, 1]
• 因為可以拿掉一個元素，代表可以將一個間隔去除
  • 計算兩個次數的加總最多即為答案
• 需要注意的部分
  • 結尾如果不是 0，也要將目前計數記下來
  • 全部都是 0，要回傳 0
  • 全部都是 1，要回傳數量減一(一樣得刪除一個)

Code

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        vector<int> oneSeq;
        int counter = 0;
        for(int i = 0; i < nums.size(); i++)
        {
            if(nums[i] == 0)
            {
                oneSeq.push_back(counter);
                counter = 0;
            }
            else
            {
                counter++;
            }
        }
        if(oneSeq.empty())
        {
            if(counter == 0)
                return 0;
            else
            {
                return counter - 1;
            }
        }
        else
            oneSeq.push_back(counter);
            
        counter = oneSeq[0];
        for(int i = 0; i < oneSeq.size() - 1; i++)
        {
            counter = max(counter, oneSeq[i] + oneSeq[i + 1]);
        }
        return counter;

    }
};

tags: LeetCode C++