一茶行、題目
給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k ，找出 nums 中和至少為 k 的 最短非空子數(shù)組 气堕，并返回該子數(shù)組的長(zhǎng)度纺腊。如果不存在這樣的 子數(shù)組 ，返回 -1 茎芭。
子數(shù)組 是數(shù)組中 連續(xù) 的一部分揖膜。
二、示例
2.1> 示例 1：
【輸入】nums = [1], k = 1
【輸出】1
2.2> 示例 2：
【輸入】nums = [1,2], k = 4
【輸出】-1
2.3> 示例 3：
【輸入】nums = [2,-1,2], k = 3
【輸出】3
提示：
-
1<= nums.length <=10^5 -
-10^5<= nums[i] <=10^5 -
1<= k <=10^9
三梅桩、解題思路
根據(jù)題目描述壹粟，我們要找到N個(gè)子序列，并且要求子序列的總和要大于等于k宿百，并且只要最短長(zhǎng)度趁仙。那么，對(duì)于一個(gè)數(shù)組有多少子序列垦页，我們首先需要確定數(shù)組子序列的起點(diǎn)雀费。那么，由于題目中只需要最短長(zhǎng)度痊焊，所以盏袄，假設(shè)我們以i為起點(diǎn)向后拼裝子序列，只要子序列總和大于等于k薄啥，則立刻結(jié)束以i為起點(diǎn)的子序列組合行為辕羽。具體如下圖所示：
為了避免不同起點(diǎn)執(zhí)行拼裝子序列會(huì)產(chǎn)生重復(fù)操作，所以垄惧，我們采取前綴和的方式刁愿，即：計(jì)算位置i之前的所有元素之和。以nums=[2, -1, 2, 3, 4]為例赘艳，對(duì)應(yīng)的前綴和就是[0, 2, 1, 3, 6, 10]酌毡。我們通過(guò)遍歷數(shù)組nums的前綴和克握，將某個(gè)元素i的前綴和放入到隊(duì)列中蕾管，這樣枷踏，從末尾執(zhí)行插入，從隊(duì)首執(zhí)行彈出掰曾。
那么旭蠕，其實(shí)對(duì)于哪些數(shù)為起點(diǎn)，也是有優(yōu)化空間的旷坦。就是說(shuō)掏熬，以下圖所示，當(dāng)我們發(fā)現(xiàn)E的前綴和sum(A-D)大于等于F的前綴和sum(A-E)秒梅，我們其實(shí)就沒(méi)必要以E為起點(diǎn)了旗芬，因?yàn)镕相比E會(huì)更適合。具體邏輯如下圖所示：
四捆蜀、代碼實(shí)現(xiàn)
class Solution {
public int shortestSubarray(int[] nums, int k) {
int result = Integer.MAX_VALUE, n = nums.length, head = 0, tail = head;
long[] preSum = new long[n + 1];
/** 步驟1：構(gòu)建前綴和 */
for (int i = 0; i < n; i++) {
if (nums[i] >= k) return 1;
preSum[i + 1] = preSum[i] + nums[i];
}
/** 步驟2：構(gòu)建單調(diào)棧和使用單調(diào)棧求最小值 */
int[] queue = new int[n + 1];
for (int i = 0; i < n + 1; i++) {
while (head != tail && preSum[queue[tail - 1]] >= preSum[i])
tail--;
queue[tail++] = i;
while (head != tail && preSum[i] - preSum[queue[head]] >= k)
result = Math.min(i - queue[head++], result);
}
return result == Integer.MAX_VALUE ? -1 : result;
}
}
今天的文章內(nèi)容就這些了：
寫(xiě)作不易疮丛，筆者幾個(gè)小時(shí)甚至數(shù)天完成的一篇文章，只愿換來(lái)您幾秒鐘的 點(diǎn)贊 & 分享 辆它。
更多技術(shù)干貨誊薄，歡迎大家關(guān)注公眾號(hào)“爪哇繆斯” ~ \(o)/ ~ 「干貨分享，每天更新」
