leetcode 862. 和至少为 K 的最短子数组
题目描述
给你一个整数数组 nums
和一个整数 k
,找出 nums
中和至少为 k
的 最短非空子数组 ,并返回该子数组的长度。如果不存在这样的 子数组 ,返回 -1
。
子数组 是数组中 连续 的一部分。
示例 1:
输入:nums = [1], k = 1 输出:1
示例 2:
输入:nums = [1,2], k = 4 输出:-1
示例 3:
输入:nums = [2,-1,2], k = 3 输出:3
提示:
1 <= nums.length <= 105
-105 <= nums[i] <= 105
1 <= k <= 109
题解——单调队列详解
今天正好趁着这道题学习了一下单调队列,把过程中我的一些理解记录下来,如有不对的地方,希望大佬们指出。
单调队列与单调栈的区别与联系
相比于单调队列,单调栈要常见得多。需要指出的是,这两者并不像栈与队列那样有着截然相反的操作(事实上,单调队列用的并不是队列,而是双端队列),在操作和功能上,单调队列其实是单调栈的扩展。单调栈的作用是快速地获取距离某个元素最近的更大(小)元素的位置。单调队列同样也有这个功能,此外,由于可以对左侧元素进行访问和处理,可以用来维护一定区间大小内的最大(小)值。也就是说,单调队列可以在队尾操作以维护单调性,并在队首操作来获取和维护区间大小。
单调队列的作用
最经典的题目就是239.滑动窗口最大值,这题,我们通过维护一个单调递减队列,在队尾维护单调性,保证队列里的>=当前数;并在队首维护窗口大小,保证队列内长度<=k,那么队首对应元素就是答案,如果没做过单调队列,应该先去做一下这题。
单调队列在此题的应用
先对数组求前缀和,这样可以把任意一段子数组的和转化为两个前缀和之差。然后我们对前缀和维护一个单调递增队列,这样队首就是前面的前缀和的最小值。如果发现当前值减去最小值>=k,就不断从队首出队,直到<k,得到以当前位置为结尾的满足条件的最短子数组**,与ans比较。
有一个问题需要说明:我们判断子数组和>=k时,就直接将当前最小值出队了,这会不会对后面产生干扰呢?是不会的,因为后面的离队首更远了**,不可能是更优解。所以最后得到的就是答案。
代码
1 | class Solution { |
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 HeRen's Blog!
评论