python-leetcode-删掉一个元素以后全为 1 的最长子数组
1493. 删掉一个元素以后全为 1 的最长子数组 - 力扣(LeetCode)
可以使用滑动窗口的方式来解决这个问题。我们要找到最长的全 1 子数组,但必须删除一个元素,因此可以将问题转化为寻找最多包含一个 0 的最长子数组。
解题思路
- 使用双指针(滑动窗口),维护窗口内最多包含一个
0
。 - 当窗口内的
0
超过 1 个时,移动左指针left
直到窗口内0
的数量恢复为 1。 - 记录窗口的最大长度,最终返回
maxLen - 1
,因为必须删除一个元素(即使数组全是1
,我们仍然需要删掉一个)。
代码实现
def longestSubarray(nums):
left = 0
zero_count = 0
max_len = 0
for right in range(len(nums)):
if nums[right] == 0:
zero_count += 1
while zero_count > 1:
if nums[left] == 0:
zero_count -= 1
left += 1
max_len = max(max_len, right - left + 1)
return max_len - 1 # 必须删除一个元素
复杂度分析
- 时间复杂度:O(n),遍历数组一次,每个元素最多进出窗口一次。
- 空间复杂度:O(1),只使用了常数额外空间。
示例
示例 1
nums = [1,1,0,1,1,1]
print(longestSubarray(nums)) # 输出: 5
解释:
- 删除
0
后,最长的1
子数组是[1,1,1,1,1]
,长度为5
。
示例 2
nums = [0,0,0]
print(longestSubarray(nums)) # 输出: 0
解释:
- 无法形成全
1
的子数组,因此返回0
。
这个方法高效且直观,适用于处理大规模数据。