删掉一个元素以后全为 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子数组的长度?
▷🦆
为什么在遍历结束后,需要再次更新最大长度`max(ans, r - l - cnt)`?这个公式中`-cnt`的目的是什么?
▷🦆
算法在处理全为1或全为0的数组时提供了特殊规则,这对算法的整体效率有何影响?
▷🦆
滑动窗口策略中,当窗口内已有一个0时,为什么需要将左指针移动到下一个0之后而不能直接跳过多个0?
▷