[LeetCode] 862. Shortest Subarray with Sum at Leas

thursday 发布于2019-08-16 13:50 / 1906人阅读

摘要：较早放入的元素在队列顶部最近放入的元素在队列尾部检查最近放入的，保证队列中新放入的及对应的均为递增反证若保留，那么在下面第二个循环，该元素有可能中断循环，并使得我们无法得到队列更左边的最优解检查较早放入的最小距离

Problem

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 <= A.length <= 50000
-10 ^ 5 <= A[i] <= 10 ^ 5
1 <= K <= 10 ^ 9

Solution

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        if (nums == null || nums.length == 0) return -1;
        int len = nums.length, min = len+1;
        int[] sum = new int[len+1];
        for (int i = 0; i < len; i++) sum[i+1] = sum[i] + nums[i];
        Deque queue = new ArrayDeque<>();
        // pollFirst() == poll()    较早放入deque的元素 在队列顶部
        // getFirst() == peek()
        // pollLast()               最近放入deque的元素 在队列尾部
        // getLast()
        for (int i = 0; i <= len; i++) {
            // 检查最近放入的index，保证队列中新放入的index及对应的sum[index]均为递增
            // 反证：若保留worse candidate，那么在下面第二个while循环，该元素有可能
            // 中断while循环，并使得我们无法得到队列更左边的最优解
            while (queue.size() > 0 && sum[i]-sum[queue.getLast()] <= 0) {
                queue.pollLast();
            }
            // 检查较早放入的index update最小距离
            while (queue.size() > 0 && sum[i]-sum[queue.peek()] >= k) {
                min = Math.min(min, i-queue.peek());
                queue.pollFirst();
            }
            
            queue.offer(i);
        }
        return min <= len ? min : -1;
    }
}

专线服务服务器托管 subarray Shortest LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72429.html

leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
[LeetCode] 523. Continuous Subarray Sum

Problem Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sum...

stackfing 2019-08-16 13:46 评论0 收藏0
[LeetCode] Maximum Subarray

Problem Find the contiguous subarray within an array (containing at least one number) which has the largest sum. Example For example, given the array [-2,1,-3,4,-1,2,1,-5,4],the contiguous subarray [4...

Donald 2019-08-15 13:40 评论0 收藏0
[Leetcode] Maximum Subarray 子序列最大和

摘要：最新更新请见原题链接动态规划复杂度时间空间思路这是一道非常典型的动态规划题，为了求整个字符串最大的子序列和，我们将先求较小的字符串的最大子序列和。而最大子序列和的算法和上个解法还是一样的。 Maximum Subarray 最新更新请见：https://yanjia.me/zh/2019/02/... Find the contiguous subarray within an ar...

summerpxy 2019-08-14 16:11 评论0 收藏0