首页 > 其他分享 >LeetCode 862.和至少为k的最短子数组

LeetCode 862.和至少为k的最短子数组

时间:2023-06-07 14:01:17浏览次数:38  
标签:nums int res 862 back 队列 短子 LeetCode 单调


LeetCode 862.和至少为k的最短子数组

本题前缀和队列并不单调,所以应该算变种单调队列,在计算出单调队列以后还要进行进一步优化,即在如下条件
LeetCode 862.和至少为k的最短子数组_leetcode
如果我们找到当前的s[i]满足条件,则说明之后选取的s[i]不管是多少,均没有当前s[i]距离s[j]近,所以在此以后的值均可以丢弃,同理,s[j]之前的值也是如此,因此经过这两轮优化,我们就可以得到一个基本的单调队列

typedef long long ll;

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        int length=nums.size();
        vector<ll> s(length+1);//前缀和
        for(int i=1;i<=length;i++)   s[i] = s[i-1] + nums[i-1];
        deque<int> q;
        q.push_back(0);
        int res = INT_MAX;
        for(int i=1;i<=length;i++)
        {
            //cout<<s[i]<<endl;
            while(q.size() && s[q.front()] + k <= s[i])
            {
                res = min(res, i-q.front());
                q.pop_front();
            }
            while(q.size() && s[q.back()] >= s[i])  q.pop_back();
            q.push_back(i);
        }
        if(res==INT_MAX)    res=-1;
        return res;
    }
};


标签:nums,int,res,862,back,队列,短子,LeetCode,单调
From: https://blog.51cto.com/u_15567308/6431287

相关文章

  • LeetCode 388.文件的最长绝对路径
    题目链接思路针对文件路径的特征,一个文件中一定包含.分隔符,以此为依据可以判定当前字符串是否是一个文件,文件系统是一个树形结构的角度来看的话,题中给定的字符串实际上是以一个树形结构前序遍历的序列,连续的\t表示出了当前的深度,而相邻的节点之间以\n进行分割。假设当前的路径为x/......
  • #yyds干货盘点# LeetCode程序员面试金典:二叉树的右视图
    1.简述:给定一个二叉树的根节点root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。 示例1:输入: [1,2,3,null,5,null,4]输出: [1,3,4]示例2:输入: [1,null,3]输出: [1,3]示例3:输入: []输出: []2.代码实现:classSolution{publicList<I......
  • #yyds干货盘点# LeetCode程序员面试金典:二叉树中的最大路径和
    题目:二叉树中的路径被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点,且不一定经过根节点。路径和是路径中各节点值的总和。给你一个二叉树的根节点root,返回其最大路径和。 示例1:输入:root=......
  • Leetcode 2352. 相等行列对
    题目:给你一个下标从0开始、大小为nxn的整数矩阵grid,返回满足\(R_i\)行和\(C_j\)列相等的行列对(\(R_i\),\(C_j\))的数目。如果行和列以相同的顺序包含相同的元素(即相等的数组),则认为二者是相等的。难度:中等示例1:输入:grid=[[3,2,1],[1,7,6],[2,7,7]]输出:1......
  • [LeetCode] 1347. Minimum Number of Steps to Make Two Strings Anagram 制造字母异
    Youaregiventwostringsofthesamelength s and t.Inonestepyoucanchoose anycharacter of t andreplaceitwith anothercharacter.Return theminimumnumberofsteps tomake t ananagramof s.An Anagram ofastringisastringthatco......
  • leetcode-图论总结
    此文总结一下常见图论算法,代码可以为后续遇见类似题目提供参考:1.图的表示:邻接矩阵:可通过创建数组得到邻接表:我个人喜欢通过LinkedList<int[]>[]graph=newLinkedList[n];得到。EdgeList:同样可以通过LinkedList<int[]>[]graph=newLinkedList[n];得到。2.图遍历:DF......
  • 树之深度优先遍历算法详解(DFS实现) LeetCode94
           本文以如下树结构为例深度优先(DeepFirstSearch)       树的孩子称作子树,对于一个树进行深度优先遍历,即将其某一子树下所有节点遍历完再去遍历其他子树。遍历的顺序以根为参照可分为先序遍历,中序遍历,后序遍历。遍历方式描述先序遍历根左右中序遍历左根右后......
  • leetcode-滑动窗口总结
    滑动窗口是我在刷题时感觉比较困难的部分,简单做一个总结,防止之后又忘了:一般模板如下://注意:java代码由chatGPT......
  • Leetcode 2460. 对数组执行操作
    题目:给你一个下标从0开始的数组nums,数组大小为n,且由非负整数组成。你需要对数组执行n-1步操作,其中第i步操作(从0开始计数)要求对nums中第i个元素执行下述指令:如果nums[i]==nums[i+1],则nums[i]的值变成原来的2倍,nums[i+1]的值变成0。否则,跳过......
  • [LeetCode] 2460. Apply Operations to an Array
    Youaregivena 0-indexed array nums ofsize n consistingof non-negative integers.Youneedtoapply n-1 operationstothisarraywhere,inthe ith operation(0-indexed),youwillapplythefollowingonthe ith elementof nums:If nums[i]......