[LeetCode] 862. Shortest Subarray with Sum at Leas

thursday 發布于2019-08-16 13:50 / 2076人閱讀

摘要：較早放入的元素在隊列頂部最近放入的元素在隊列尾部檢查最近放入的，保證隊列中新放入的及對應的均為遞增反證若保留，那么在下面第二個循環，該元素有可能中斷循環，并使得我們無法得到隊列更左邊的最優解檢查較早放入的最小距離

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;
    }
}

云服務器 GPU云服務器 subarray Shortest LeetCode LeetCode_String

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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