侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【前缀和, 单调队列】和至少为 K 的最短子数组

GabrielxD
2022-05-16 / 0 评论 / 1 点赞 / 71 阅读 / 836 字 / 正在检测是否收录...

题目

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


给你一个整数数组 nums 和一个整数 k ,找出 nums 中和至少为 k 的 最短非空子数组 ,并返回该子数组的长度。如果不存在这样的 子数组 ,返回 -1

子数组 是数组中 连续 的一部分。

示例 1:

输入:nums = [1], k = 1
输出:1

示例 2:

输入:nums = [1,2], k = 4
输出:-1

示例 3:

输入:nums = [2,-1,2], k = 3
输出:3

提示:

  • 1 <= nums.length <= 10^5
  • -10^5 <= nums[i] <= 10^5
  • 1 <= k <= 10^9

解题

方法一: 前缀和 单调队列

思路

将问题从 “找出 nums 和至少为 k最短非空子数组” 转化为 “找出(nums的)前缀和数组中距离最近且相减至少为 k 的两数”。

维护一个 nums前缀和数组(prefixSumArr),一个单调递增队列(monoDeque),存储前缀和数组(prefixSumArr)中的索引,初始化 ans
开始遍历前缀和数组:

  • 如果队列不为空且「当前遍历到的前缀和(currPrefixSum)」 \le队列尾部的前缀和」,说明「队列尾部的前缀和」已经有距离另一个前缀和更近作差更大的替代品了,可以直接让它出队,原因:

    • 因为遍历是正向进行的,所以「当前遍历到前缀和」一定比「队列尾部的前缀和」更靠右,也就更靠近下一个前缀和。
    • 因为「当前遍历到前缀和」值更小,所以与另一个前缀和作差时得到的值更大,也就更容易大于等于 k,也就更有可能是一个合法解的一部分。
    • 由前两点可以得知此时「队列尾部的前缀和」已经有了更好的替代品,所以可以直接让他出队。
    • 循环,直到「当前遍历到前缀和」更小。
  • 如果队列不为空且「当前遍历到前缀和」 \ge队列头部的前缀和」+ k,说明这组前缀和是一组合法的解,把队列头部的索引出队,把它们作差表示的子数组的长度(i - monoDeque.poll()),更新 ans 使其保持有效解中的最小长度。

    • 循环,直到这「当前遍历到前缀和」与「队列头部的前缀和」作差小于 k,也就不是一组合法解了。
  • 把当前索引从队尾入队。

最后,如果 ans 被更新到了小于等于 len 的长度,也就说明找到了最短子数组,直接返回 ans,反之没找到返回 -1

代码

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int len = nums.length;
        long[] prefixSumArr = new long[len + 1];
        for (int i = 0; i < len; i++) {
            prefixSumArr[i + 1] = prefixSumArr[i] + (long) nums[i];
        }
        int ans = Integer.MAX_VALUE;
        Deque<Integer> monoDeque = new LinkedList<>();
        for (int i = 0; i < len + 1; i++) {
            int currPrefixSum = prefixSumArr[i];
            while (!monoDeque.isEmpty() &&
                   currPrefixSum <= prefixSumArr[monoDeque.peekLast()]) {
                monoDeque.pollLast();
            }
            while (!monoDeque.isEmpty() &&
                   currPrefixSum >= prefixSumArr[monoDeque.peek()] + k) {
                ans = Math.min(ans, i - monoDeque.poll());
            }
            monoDeque.offer(i);
        }
        return ans > len ? -1 : ans;
    }
}
1

评论区