0862. 和至少为 K 的最短子数组
大约 4 分钟
---
0862. 和至少为 K 的最短子数组
- 标签:队列、数组、二分查找、前缀和、滑动窗口、单调队列、堆(优先队列)
- 难度:困难
题目链接
题目大意
描述:给定一个整数数组 和一个整数 。
要求:找出 中和至少为 的最短非空子数组,并返回该子数组的长度。如果不存在这样的子数组,返回 。
说明:
- 子数组:数组中连续的一部分。
- 。
- 。
- 。
示例:
- 示例 1:
输入:nums = [1], k = 1
输出:1
- 示例 2:
输入:nums = [1,2], k = 4
输出:-1
解题思路
思路 1:前缀和 + 单调队列
题目要求得到满足和至少为 的子数组的最短长度。
先来考虑暴力做法。如果使用两重循环分别遍历子数组的开始和结束位置,则可以直接求出所有满足条件的子数组,以及对应长度。但是这种做法的时间复杂度为 。我们需要对其进行优化。
1. 前缀和优化
首先对于子数组和,我们可以使用「前缀和」的方式,方便快速的得到某个子数组的和。
对于区间 ,通过 即可快速求解出区间 的子数组和。
此时问题就转变为:是否能找到满足 且 两个条件的子数组 ?如果能找到,则找出 差值最小的作为答案。
2. 单调队列优化
对于区间 来说,我们应该尽可能的减少不成立的区间枚举。
- 对于某个区间 来说,如果 ,那么大于 的索引值就不用再进行枚举了,不可能比 的差值更优了。此时我们应该尽可能的向右移动 ,从而使得 更小。
- 对于某个区间 来说,如果 ,对于任何大于等于 的索引值 来说, 一定比 更小且长度更小,此时 可以直接忽略掉。
因此,我们可以使用单调队列来维护单调递增的前缀数组 。其中存放了下标 ,满足 单调递增。
- 使用一重循环遍历位置 ,将当前位置 存入倒掉队列中。
- 对于每一个位置 ,如果单调队列不为空,则可以判断其之前存入在单调队列中的 值,如果 ,则更新答案,并将 从队头位置弹出。直到不再满足 时为止(即 )。
- 如果队尾 ,那么说明以后无论如何都不会再考虑 了,则将其从队尾弹出。
- 最后遍历完返回答案。
思路 1:代码
class Solution:
def shortestSubarray(self, nums: List[int], k: int) -> int:
size = len(nums)
# 优化 1
pre_sum = [0 for _ in range(size + 1)]
for i in range(size):
pre_sum[i + 1] = pre_sum[i] + nums[i]
ans = float('inf')
queue = collections.deque()
for i in range(size + 1):
# 优化 2
while queue and pre_sum[i] - pre_sum[queue[0]] >= k:
ans = min(ans, i - queue.popleft())
while queue and pre_sum[queue[-1]] >= pre_sum[i]:
queue.pop()
queue.append(i)
if ans == float('inf'):
return -1
return ans
思路 1:复杂度分析
- 时间复杂度:,其中 为数组 的长度。
- 空间复杂度:。