1696. 跳跃游戏 VI - 力扣（LeetCode）
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
一开始你在下标 0 处。每一步，你最多可以往前跳 k 步，但你不能跳出数组的边界。也就是说，你可以从下标 i 跳到 [i + 1， min(n - 1, i + k)] 包含 两个端点的任意位置。
你的目标是到达数组最后一个位置（下标为 n - 1 ），你的 得分 为经过的所有数字之和。
请你返回你能得到的 最大得分 。
解题思路
这里使用单调队列，维护队首是最大值，和使用大顶堆原理都是一样的。直接看例子就懂了。
代码实现
class Solution {
public:
int maxResult(vector<int>& nums, int k) {
int n = nums.size();
deque<pair<int,int>> q;
q.emplace_back(nums[0],0);
int ans = nums[0];
for(int i = 1; i < n; i++){
while(i - q.front().second > k){
q.pop_front();
}
ans = q.front().first + nums[i];
while(!q.empty() && ans >= q.back().first){
q.pop_back();
}
q.emplace_back(ans,i);
}
return ans;
}
};918. 环形子数组的最大和 - 力扣（LeetCode）
给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。
环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。
子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], ..., nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。
解题思路
前缀和+单调队列。这道题和上题很类似，首先将数组延长一倍，转换为在一个长度为2n的数组上，寻找长度不超过n的最大子数组和。而子数组和又转化为了前缀和的问题。需注意出列条件的区别。具体实现见代码。
代码实现
class Solution {
public:
int maxSubarraySumCircular(vector<int>& nums) {
int n = nums.size();
deque<pair<int,int>> q;
int preSum = nums[0], res = nums[0];
q.emplace_back(0,preSum);
for(int i = 1; i < 2*n; i++){
if(!q.empty() && i - q.front().first > n){
q.pop_front();
}
preSum += nums[i%n];
res = max(res, preSum-q.front().second);
while(!q.empty() && q.back().second >= preSum){
q.pop_back();
}
q.emplace_back(i,preSum);
}
return res;
}
};862. 和至少为 K 的最短子数组 - 力扣（LeetCode）
给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。
子数组 是数组中 连续 的一部分。
解题思路
前缀和+单调队列。同样也是维护双端队列的单调性，在本题中，条件是求最短子数组的长度。那么如何在满足题干条件的前提下缩短子数组长度呢？分两种情况，举例分析：（随便假定的数据，大体是这么理解）
代码实现
class Solution {
public:
int shortestSubarray(vector<int>& nums, int k) {
int n = nums.size();
int res = INT_MAX;
vector<long> preSum(n+1);
for (int i = 1; i <= n; ++i) {
preSum[i] = preSum[i-1] + nums[i-1];
}
deque<int> q;
q.push_back(0);
for(int i = 1; i <= n; i++){
while(!q.empty() && preSum[i] - preSum[q.front()] >= k){
res = min(res, i - q.front());
q.pop_front();
}
while(!q.empty() && preSum[q.back()] >= preSum[i]){
q.pop_back();
}
q.push_back(i);
}
return res == INT_MAX ? -1 : res;
}
};