题目描述

leetcode862. 和至少为 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        deque<int> dq;//单调递增双端队列
        int ans=INT_MAX;
        vector<long> preSum(nums.size()+1);
        for(int i=0;i<nums.size();++i)//求前缀和，注意要在开头多添加一个0
            preSum[i+1]=preSum[i]+nums[i];
        for(int i=0;i<preSum.size();++i)
        {
            while(!dq.empty()&&preSum[i]-preSum[dq.front()]>=k)//当有满足条件的子数组时，一直得到最短的
            {
                ans=min(ans,i-dq.front());
                dq.pop_front();
            }
            while(!dq.empty()&&preSum[dq.back()]>=preSum[i])//在队尾维护单调性
                dq.pop_back();
            dq.push_back(i);
        }
        return ans==INT_MAX?-1:ans;
    }
};