1493. 删掉一个元素以后全为 1 的最长子数组
难度中等20
给你一个二进制数组 nums ，你需要从中删掉一个元素。
请你在删掉元素的结果数组中，返回最长的且只包含 1 的非空子数组的长度。
如果不存在这样的子数组，请返回 0 。
/*
相似题目 424,1493,1004.
二分法
https://github.com/kingeasternsun/leetcode-cn
*/
func longestSubarrayBinary(nums []int) int {
start := 0
end := len(nums)
best := -1
for start <= end {
mid := (end-start)/2 + start
if judege(nums, mid) {
best, start = mid, mid+1
} else {
end = mid - 1
}
}
if best > 0 {
return best - 1
}
return best
}
func judege(nums []int, winLen int) bool {
numCnt := [2]int{}
for i := 0; i < winLen; i++ {
numCnt[nums[i]]++
}
if numCnt[0] <= 1 {
return true
}
for i := winLen; i < len(nums); i++ {
numCnt[nums[i-winLen]]--
numCnt[nums[i]]++
if numCnt[0] <= 1 {
return true
}
}
return false
}
func longestSubarray(nums []int) int {
maxLen := 0
numCnt := [2]int{}
beg, end := 0, 0 //左闭右开区间
for beg <= end && end < len(nums) {
//如果当前end上是1 或 [beg,end)里面没有0 ，就可以把 当前end加入窗口
if nums[end] == 1 || numCnt[0] == 0 {
numCnt[nums[end]]++
end++
if end-beg-1 > maxLen {
maxLen = end - beg - 1
}
continue
}
//end上是0 ,而且 [beg,end)里面已经有一个0了，就需要去掉左边的beg
numCnt[nums[beg]]--
beg++
}
return maxLen
}