本文主要是介绍LeetCode862. Shortest Subarray with Sum at Least K——单调队列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文章目录
- 一、题目
- 二、题解
一、题目
Given an integer array nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum of at least k. If there is no such subarray, return -1.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [1], k = 1
Output: 1
Example 2:
Input: nums = [1,2], k = 4
Output: -1
Example 3:
Input: nums = [2,-1,2], k = 3
Output: 3
Constraints:
1 <= nums.length <= 105
-105 <= nums[i] <= 105
1 <= k <= 109
二、题解
class Solution {
public:int shortestSubarray(vector<int>& nums, int k) {int n = nums.size();deque<int> q;int res = INT_MAX;vector<long long> sum(n+1,0);for(int i = 0;i < n;i++){sum[i+1] = sum[i] + nums[i];}for(int r = 0;r <= n;r++){while(!q.empty() && sum[r] - sum[q.front()] >= k){res = min(res,r - q.front());q.pop_front();}while(!q.empty() && sum[q.back()] >= sum[r]) q.pop_back();q.push_back(r);}return res == INT_MAX ? -1 : res;}
};
这篇关于LeetCode862. Shortest Subarray with Sum at Least K——单调队列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
