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

leetcode medium

#array#backtracking#csharp#leetcode#math#medium#sliding-window

Task

Дан бинарный массив nums, из которого следует удалить один элемент.

Верните размер самой длинной непустой подмассивы, содержащей только 1, в результирующем массиве. Верните 0, если такого подмассива не существует.

Пример:

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].

C# solution

matched/original

public class Solution {
    public int LongestSubarray(int[] nums) {
        int zeroCount = 0;
        int longestWindow = 0;
        int start = 0;
        for (int i = 0; i < nums.Length; i++) {
            if (nums[i] == 0) {
                zeroCount++;
            }
            while (zeroCount > 1) {
                if (nums[start] == 0) {
                    zeroCount--;
                }
                start++;
            }
            longestWindow = Math.Max(longestWindow, i - start);
        }
        return longestWindow;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int LongestSubarray(vector<int>& nums) {
        int zeroCount = 0;
        int longestWindow = 0;
        int start = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 0) {
                zeroCount++;
            }
            while (zeroCount > 1) {
                if (nums[start] == 0) {
                    zeroCount--;
                }
                start++;
            }
            longestWindow = max(longestWindow, i - start);
        }
        return longestWindow;
    }
}

Java solution

auto-draft, review before submit

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public int LongestSubarray(int[] nums) {
        int zeroCount = 0;
        int longestWindow = 0;
        int start = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                zeroCount++;
            }
            while (zeroCount > 1) {
                if (nums[start] == 0) {
                    zeroCount--;
                }
                start++;
            }
            longestWindow = Math.max(longestWindow, i - start);
        }
        return longestWindow;
    }
}

Go solution

matched/original

func longestSubarray(nums []int) int {
    zeroCount := 0
    longestWindow := 0
    start := 0

    for i := 0; i < len(nums); i++ {
        if nums[i] == 0 {
            zeroCount++
        }

        for zeroCount > 1 {
            if nums[start] == 0 {
                zeroCount--
            }
            start++
        }

        longestWindow = max(longestWindow, i - start)
    }

    return longestWindow
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Explanation

Algorithm

Инициализация переменных:

zeroCount для подсчёта нулей в текущем окне, longestWindow для хранения максимальной длины окна, содержащего не более одного нуля, и start для левой границы окна.

Итерация по массиву:

При каждом элементе увеличиваем zeroCount, если это ноль.

Если zeroCount превышает 1, сокращаем окно, перемещая левую границу вправо и уменьшая zeroCount, пока количество нулей не станет меньше или равно 1.

Обновляем longestWindow текущей длиной окна i - start.

Возврат результата:

Вернуть longestWindow.

😎