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就不需要了
这样做到最后就可以得到答案