24年保研暑假：编程细节和方法

一、前缀和初始化问题

在使用前缀和时，我们容易忽略前缀为空时的情况，也就是说[0,i]的和的情况，因此我们使用前缀和时需要构造一个和为0，下标为-1的前缀和。记住！

二、单调队列可以存储下标

我们单调队列维护单增序列或单减序列，并不一定队列中就要存储数值，可以存储数值对应的下标。（自己选择）

比如我们来考察稍微复杂的问题：LeetCode： 862. 和至少为 K 的最短子数组，和直接使用单调队列不一样，这个问题还是在使用了前缀和的基础上使用单调队列的。

以下是官解代码：

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<long> preSumArr(n + 1);
        for (int i = 0; i < n; i++) {
            preSumArr[i + 1] = preSumArr[i] + nums[i];
        }
        int res = n + 1;
        deque<int> qu;
        for (int i = 0; i <= n; i++) {
            long curSum = preSumArr[i];
            while (!qu.empty() && curSum - preSumArr[qu.front()] >= k) {
                res = min(res, i - qu.front());
                qu.pop_front();
            }
            while (!qu.empty() && preSumArr[qu.back()] >= curSum) {
                qu.pop_back();
            }
            qu.push_back(i);
        }
        return res < n + 1 ? res : -1;
    }
};

我们注意到它先把前缀和求了出来，像我们之前说的那样也预留了一个空值（0）。它之所以先把前缀和求出来的原因是，由于我们要求的是区间长度，最终还是需要知道下标的，如果我们选择不直接求出来，我们就必须与单调队列同时维护一个原数组对应下标的单调队列，同样需要新空间。

当然在这里维护两个单调队列（一个数值一个下标）也是可以的，因为使用的空间差不多，只是后续实现起来会显得代码更长。

vector<long> preSumArr(n + 1);
for (int i = 0; i < n; i++) {
    preSumArr[i + 1] = preSumArr[i] + nums[i];
}

原文地址：https://blog.csdn.net/m0_63997099/article/details/141373403

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！