Re: [閒聊] 每日leetcode
862. Shortest Subarray with Sum at Least K
長度為n的矩陣nums
和一個整數k
請回傳最長的subarray長度
該subarray所有元素的總和>=k
思路:
因為nums會有負數
所以用sliding windows會出問題
有兩個做法
(1)
用最小堆，最小堆裡面放的是[i,sum[i]]
先用sum記錄到j的總和
接著從0~n-1
把最小堆裡面滿足 sum[j] - sum[i]>=k的元素全部pop出來
並且維護answer=min(answer,j-i)
再把[j,sum[j]] push到最小堆裡面
這樣就可以得到答案了
(2)
用prefix sum + dequeue
先建立prefix_sum array
dequeue裡面放的是nums的index
接著0~n
把滿足prefix_sum[i]-prefix_sum[dequeue[0]]的元素
從dequeue裡pop出來
並且維護answer=min(answer,i-dequeue[0])
接著把滿足prefix_sum[i]<=prefix_sum[dequeue[dequeue.length-1]]
從dequeue pop出來
要這麼做是因為在prefix_sum[j] <= prefix_sum[i] (j>i)的情況下
如果有一個k滿足prefix_sum[k]-prefix_sum[i] >= k (k>j>i)
那這個k也一定滿足prefix_sum[k]-prefix_sum[j] >= k
而且k-j < k-i
所以i就不需要了
這樣做到最後就可以得到答案
-------------------------------------
code 是第二種方式
golang code :
func shortestSubarray(nums []int, k int) int {
n := len(nums)
prefixsum := make([]int, n+1)
for i := 0; i < n; i++ {
prefixsum[i+1] = prefixsum[i] + nums[i]
}
array, ans := []int{}, n+1
for i := 0; i <= n; i++ {
for len(array) > 0 && prefixsum[i] <= prefixsum[array[len(array)-1]] {
array = array[:len(array)-1]
}
for len(array) > 0 && prefixsum[i]-prefixsum[array[0]] >= k {
ans = min(ans, i-array[0])
array = array[1:]
}
array = append(array, i)
}
if ans > n {
return -1
}
return ans
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.70.178 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1731825534.A.6CD.html
討論串 (同標題文章)
完整討論串 (本文為第 1130 之 1554 篇)：