1696. 跳跃游戏 VI – 力扣（LeetCode）
给你一个下标从0开始的整数数组nums和一个整数k。
一开始你在下标0处。每一步，你最多可以往前跳k步，但你不能跳出数组的边界。也就是说，你可以从下标i跳到[i + 1， min(n - 1, i + k)]包含两个端点的任意位置。
你的目标是到达数组最后一个位置（下标为n - 1），你的得分为经过的所有数字之和。
请你返回你能得到的最大得分。
解题思路
这里使用单调队列，维护队首是最大值，和使用大顶堆原理都是一样的。直接看例子就懂了。
代码实现
class Solution {
public:
int maxResult(vector& nums, int k) {
int n = nums.size();
deque> q;
q.emplace_back(nums[0],0);
int ans = nums[0];
for(int i = 1; i 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 % n == k2 % n。
解题思路
前缀和+单调队列。这道题和上题很类似，首先将数组延长一倍，转换为在一个长度为2n的数组上，寻找长度不超过n的最大子数组和。而子数组和又转化为了前缀和的问题。需注意出列条件的区别。具体实现见代码。
代码实现
class Solution {
public:
int maxSubarraySumCircular(vector& nums) {
int n = nums.size();
deque> q;
int preSum = nums[0], res = nums[0];
q.emplace_back(0,preSum);
for(int i = 1; i n){
q.pop_front();
}
preSum += nums[i%n];
res = m服务器托管网ax(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& nums, int k) {
int n = nums.size();
int res = INT_MAX;
vector preSum(n+1);
for (int i = 1; i q;
q.push_back(0);
for(int i = 1; i = 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;
}
};服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
稀疏矩阵是一种特殊的矩阵，其非零元素数目远远少于零元素数目，并且非零元素分布没有规律。这种矩阵在实际应用中经常出现，例如在物理学、图形学和网络通信等领域。 稀疏矩阵其实也可以和一般的矩阵一样处理，之所以要把它区分开来进行特殊处理，是因为：一方面稀疏矩阵的存储空…
