leetcode
leetcode 1351 ~ 1400
删掉一个元素以后全为 1 的最长子数组

删掉一个元素以后全为 1 的最长子数组

难度:

标签:

题目描述

代码结果

运行时间: 44 ms, 内存: 20.0 MB


/*
 * Problem: Given a binary array nums, you need to delete one element from it.
 * Return the length of the longest non-empty subarray containing only 1's in the resulting array.
 * If there is no such subarray, return 0.
 * 
 * Approach using Java Streams:
 * 1. Convert the array to a list of lengths of consecutive 1's segments.
 * 2. Calculate the maximum possible length by considering the deletion of one 0.
 */

import java.util.List;
import java.util.ArrayList;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {
    public int longestSubarray(int[] nums) {
        List<Integer> segments = new ArrayList<>();
        int count = 0;
        for (int num : nums) {
            if (num == 1) {
                count++;
            } else {
                segments.add(count);
                count = 0;
            }
        }
        segments.add(count); // Add the last segment

        if (segments.size() == 1) {
            return segments.get(0) == nums.length ? nums.length - 1 : segments.get(0);
        }

        int maxLength = IntStream.range(0, segments.size() - 1)
            .map(i -> segments.get(i) + segments.get(i + 1))
            .max()
            .orElse(0);

        return maxLength + 1;
    }
}

解释

方法:

这道题解采用了滑动窗口的策略来找出最长的全1子数组,即使其中包含一个0。算法维护了三个指针l(左边界)和r(右边界),以及cnt,用于记录窗口内0的个数。遍历数组时,当遇到0且cnt为0,cnt加1,表示窗口内可以包含一个0;如果再次遇到0,则需要调整左边界l,直到窗口内的0的数量减少到1。这通过将左边界移动到下一个0之后来实现。在每次右边界r移动时,都会尝试更新最大长度ans。特殊情况处理:如果数组全为1,则删除一个元素后的长度为n-1;如果数组全为0,则返回0。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
在算法中,如果数组中只有一个0,删除这个0后如何确保正确计算最长全1子数组的长度?
当数组中只有一个0时,滑动窗口的策略会在遇到这个0时将cnt设置为1,然后继续扩展右边界r直到数组末尾。因为只有一个0,左边界l不会移动直到遍历结束。算法最后在循环外通过表达式`max(ans, r - l - cnt)`来计算最长的全1子数组长度,其中`cnt`=1表示存在一个0,从而确保计算出正确的最长全1子数组长度。
🦆
为什么在遍历结束后,需要再次更新最大长度`max(ans, r - l - cnt)`?这个公式中`-cnt`的目的是什么?
在遍历结束后,需要再次更新最大长度来确保最后一个潜在的最长子数组被考虑。特别是如果最长的全1子数组在数组的末尾或包含数组末尾的部分,这种情况下,窗口的右边界r已经到达数组的末尾而左边界l可能还未更新,因此需要计算最后一次的子数组长度。公式中的`-cnt`是为了从长度中减去窗口内0的数量,因为我们需要计算的是全1的子数组长度。
🦆
算法在处理全为1或全为0的数组时提供了特殊规则,这对算法的整体效率有何影响?
提供特殊规则对于全为1或全为0的数组能够直接返回结果,大大提高了算法的效率,因为这避免了不必要的遍历和计算。这种预处理步骤可以快速处理边缘情况,使算法更加高效和直观。
🦆
滑动窗口策略中,当窗口内已有一个0时,为什么需要将左指针移动到下一个0之后而不能直接跳过多个0?
滑动窗口的目的是维持窗口内最多一个0的条件。当窗口内已有一个0,再遇到新的0时,需要将左指针移动到第一个0之后,以确保窗口内只保留一个0。这样做可以简化逻辑,并确保每次只处理一个0的情况,避免复杂的多0处理。直接跳过多个0可能会错过有效的全1子数组,因为这些子数组可能包括部分被跳过的0之间的区间。

相关问题