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就不需要了
這樣做到最後就可以得到答案