862. 和至少为 K 的最短子数组.md

862. 和至少为 K 的最短子数组

题目传送门

点击这里

解题思路

这道题比较好的一道题，通过分析来对数据结构进行选型，是思考比较难，但如果路子清晰就很明朗的一道题。说下思路，首先根据题意看要找一段子数组满足和至少为k，这种情况不难想到肯定要用前缀和来做求每一段和值好进行比较，但如何去维护一个最短的长度是难点，一点点分析，我们构建好前缀和数组后，从头开始遍历，假设从某一处i开始用preSum[i]-preSum[j] >= k计算到j的长度已经满足条件，那么i继续向后的就没必要对j进行计算了，所以当第一次遍历到i就是以j开头的最短满足条件的长度，这时候就可以将j的前缀和删掉，还有另外一种情况，假设从j < i，如果当前的preSum[i]要是小于preSum[j]的话，那么后面的某一个k处，preSum[k]减去preSum[i]带来的收益更大，且长度最小，所以需要一种数据结构是从首和尾都删除元素的，且排序添加，所以使用单调双端队列。

代码

func shortestSubarray(nums []int, k int) int {
    n := len(nums)
    // 前缀和
    preSum := make([]int, n+1)
    for i, v := range nums {
        preSum[i+1] = preSum[i] + v
    }
    res := n + 1
    q := []int{}
    for i, v := range preSum {
        // 如果队首的前缀和到当前i位置这一段满足大于k，则计算长度，后续遇见再大的前缀和，也满足条件，都不是最小的，因为其长度一定会大于i-q[0]
        for len(q) > 0 && v - preSum[q[0]] >= k {
            res = min(res, i-q[0])
            // 出队列
            q = q[1:]
        }
        // 从队尾，即最大端开始将前缀和大于v的都剔除，因为从这些任何一个大于v的位置开始，都不如从v开始带来的收益多，而且长度也会更大。
        for len(q) > 0 && preSum[q[len(q)-1]] >= v {
            q = q[:len(q)-1]
        }
        q = append(q, i)
    }
    if res < n+1 {
        return res
    }
    return -1
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}