1

我正在研究Sum at Least K 的 Shortest Subarray问题，其中最佳解决方案使用双端队列。

由于数组可以同时具有正值和负值，因此使用双指针技术将不起作用。我理解为什么 2 指针技术不起作用。

我对使用双端队列的最佳解决方案的理解如下：

  • 在此解决方案中，最短子数组的所有可能起始值都保存在双端队列中。
  • 双端队列存储数组的前缀总和值，以便我们可以在恒定时间内计算起始元素和当前元素之间的总和。
  • 双端队列是单调递增的，因为如果我们有一个prefix = [a, b, c]and prefix[b] < prefix[a]then(c-b) > (c-a)和 since[b,c]小于[a,b,c]双端队列是单调递增的。

总和至少为 k 的最短子数组的代码如下：

public int shortestSubarray(int[] a, int k) {
    Deque<Integer> deque = new LinkedList<>();
    int res = a.length+1;
    
    int[] prefix = new int[a.length+1];
    for(int i = 1; i<prefix.length; i++)
        prefix[i] = prefix[i-1] + a[i-1];
    
    for(int i = 0; i<prefix.length; i++) {
        // increment start pointer when condition is violated 
        // this first while loop is same as what happens in the 2 pointer approach
        while(!deque.isEmpty() && prefix[i] - prefix[deque.peekLast()] >= k) {
            res = Math.min(res, i - deque.peekLast());
            deque.removeLast();
        }
        
        // this is what changes the solution from 2 pointer
        // we filter out candidates that cannot be the start for min subarray
        while(!deque.isEmpty() && prefix[i] <= prefix[deque.peekFirst()]) {
            deque.removeFirst();
        }
        
        deque.addFirst(i);
    }
    
    return res == a.length+1? -1 : res;
}

我想我理解为什么这个特定的解决方案有效，但是我仍然对何时可以使用双端队列来优化滑动窗口问题感到困惑。

我的问题

我开始思考如果问题是找到总和至少为 K 的最长子数组而不是最短子数组会发生什么变化。

  1. 如果我将问题更改为需要找到总和至少为 K 的最长子数组，我还能以类似的方式使用双端队列吗？
  2. 如果可以使用双端队列，解决方案会是什么样子？你如何解释所有不同的起始位置？我们可以尝试将其设为单调递减队列，但我认为这不能解决问题。
  3. 如果不能使用双端队列在 O(n) 时间内解决问题，那么有人可以给我一个令人信服的论据，说明为什么不能使用双端队列在 O(n) 时间内解决问题吗？

谢谢。

4

0 回答 0