跳转至

862.Shortest Subarray with Sum at Least K

Tags: Hard Queue

Links: https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/

Return the length of the shortest, non-empty, contiguous subarray of A with sum at least K.

If there is no non-empty subarray with sum at least K, return -1.

Example 1:

Input: A = [1], K = 1
Output: 1

Example 2:

Input: A = [1,2], K = 4
Output: -1

Example 3:

Input: A = [2,-1,2], K = 3
Output: 3

Note:

  1. 1 <= A.length <= 50000
  2. -10 ^ 5 <= A[i] <= 10 ^ 5
  3. 1 <= K <= 10 ^ 9
class Solution {
public:
    int shortestSubarray(vector<int>& A, int K) {
        int n = A.size();
        vector<int> sum(n + 1, 0);
        sum[0] = A[0];
        deque<int> q;
        int res = INT_MAX;
        for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + A[i - 1];
        for (int i = 0; i <= n; ++i) {
            //在一个单调区间内查找
            while (!q.empty() && sum[i] - sum[q.front()] >= K) {
                res = min(res, i - q.front());
                q.pop_front();
            }
            //维护单调区间
            while (!q.empty() && sum[i] < sum[q.back()]) {
                q.pop_back();
            }
            q.push_back(i);
        }

        return res == INT_MAX ? -1 : res;
    }
};

参考之前接雨水等类似问题，在一维数组中进行搜索的时候，一个常见的思路是寻找**单调的区间**。同时题目里明确指出涉及子数组，那么一个常用的技巧就是**前缀和**。所以顺着这个思路考虑如何利用单调区间和前缀和来解题。

第一个考虑的就是为什么要构造单调区间？它是升序的还是降序的？单调区间存储的是什么？

定义 $$ P[i] = A[0] + A[1] + ... + A[i-1] $$ 我们想要求的便是最小的 y-x，y>x 并且P[y] - P[x] >= K。

opt(y)是使得当$ P[x] <= P[y] - K $时 x 能取到的最大值。

如果有 x1<x2 并且$ P[x2]<=P[x1]，那么opt(y)一定不是 x1，因为如果有P[x1] <= P[y] - K，那么 P[x2] <= P[x1] <= P[y] - K，但是 ，但是 y - x2 更小。这表明对于opt(y)opt(y)opt(y)opt(y)的候选的候选，但是 ，但是 y - x2 更小。这表明对于opt(y)opt(y)opt(y)opt(y)的候选的候选x应该是在使P(x)递增的区间去找。要注意这里的P[x1]指的是从0到X1的数组元素之和，不是单单指一个x1$位置上元素的值。

单调区间让搜索只需要考虑首尾而可以暂时忽略区间中的信息。单调区间应该存储的是下标，因为我们要考虑的是子数组的长度最小，我让单调区间的首位是下标，那么首尾对应的前缀和的差值恰好满足题目条件，则很容易继续缩小区间进行搜索（让首端右移继续搜索）。升序比较符合一般的写法。（降序就是插入元素和删除元素的顺序改变了）

对于数组搜索，一个必然的做法肯定是从第一个元素到最后一个元素进行访问。访问到下标y的时候，我们有已知信息和未知信息。所以接下来的做法是如何处理已知信息和未知信息。

处理已知信息

这时我们维护的单调区间满足单调上升，如果P[y] - P[x] \geq K，那么x = x + 1相当于右移区间左端，看是否仍符合差值大于K。那么去掉x后面是否还会继续被使用到呢?

如果opt(y1)=x, 那么不需要再次考虑x。因为如果我们找到某些y2>y1并且opt(y2)=x，那么这表明这个解答 y2-x 是比之前的解答 $y1-x $是更坏的答案。

处理未知信息

当访问到下一个未知元素的时候，我们需要考虑它对前面的已知信息造成什么影响。显然如果它小于P[y]，就破坏了单调区间，所以就该把尾部的元素去掉，直到满足新加入的元素可以继续保持区间单调。很自然的一个疑问是，那些被去掉的元素会不会后面还会继续用到，比如我去掉了y，后面可能存在某一个y1，恰好让y1-y取到最小值呢？也不会！因为不妨假设此时y和x是已知信息里面已经搜寻完毕不再变化后的状态，之前只有x的状态会改变，也已经证明了x的改变不会影响搜索。现在假设有一y1，有 $$ y1 > y \ P[y1] < P[y] \ P[y1] \geq P[x]\ $$ 也就是它会造成尾端需要去除一些元素来继续维持单调。假设我们有一位置y2，满足 $$ y2 > y1 \ P[y2] > P[y] \ $$ 假如需要利用y的信息，恰好满足P[y2]-P[y] \geq K，因为P[y1] <P[y]，很显然P[y2] -P[y1]\geq K，区间长度更小，所以去掉的元素不用考虑。

根据思路选取数据结构

由于操作只在首尾进行，并且长度在动态变化，那么双端队列显然是最佳选择。余下代码只需注意前缀和的求取细节和判断条件的符号即可写出正确代码。