(队列) LeetCode862. 和至少为 K 的最短子数组

题目:
返回 A 的最短的非空连续子数组的长度,该子数组的和至少为 K 。
如果没有和至少为 K 的非空子数组,返回 -1 。

示例 1:
输入:A = [1], K = 1
输出:1
示例 2:
输入:A = [1,2], K = 4
输出:-1
示例 3:
输入:A = [2,-1,2], K = 3
输出:3

方法 双指针
思路:

1.创建一个数组,其中P[i] = A[0]+A[1]+ ...+ A[i](如果A[i]没有负数可以保证P[i+1]>P[i])则本题转换为P[y]-P[x]>=k且y-x最小的值
2.使用双端队列保存滑动窗口值(js可以直接使用数组),每次循环在队列尾添加本次循环的下标j,记为滑动窗口末尾值,为了保证P[j+1]>P[j],因此while(queue.length!=0 && P[queue[queue.length-1]] >=P[j]){queue.pop()},当queue.length!=0 && P[j]-P[queue[0]]>=K时判断最新的滑动窗口初始值
作者:witch
链接:https://leetcode-cn.com/problems/shortest-subarray-with-sum-at-least-k/solution/jsban-ben-de-hua-dong-chuang-kou-by-witch/
来源:力扣(LeetCode)

时间复杂度O(n)
空间复杂度O(n)


var shortestSubarray = function(A, K) {
    let len = A.length;
    let min = len + 1;
    let quene = [];
    let P = new Array(len).fill(0);
    for(let i = 0; i < len; i++){
        P[i + 1] = A[i] + P[i];
    }
    for(let j = 0; j <= len; j++){
        while(quene.length && P[quene[quene.length - 1]] > P[j]){
            quene.pop()
        }   
        while(quene.length &&  P[j] - P[quene[0]] >= K){
            min = Math.min(min, j - quene[0])
            quene.shift();
        }   
        quene.push(j);
    }
    return min < len + 1 ? min : -1;       
};
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容