java - 具有线性时间复杂度的嵌套循环？

Question

public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    if (n == 0) {
        return nums;
    }
    int[] result = new int[n - k + 1];
    LinkedList<Integer> dq = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (!dq.isEmpty() && dq.peek() < i - k + 1) {
            dq.poll();
        }
        while (!dq.isEmpty() && nums[i] >= nums[dq.peekLast()]) {
            dq.pollLast();
        }
        dq.offer(i);
        if (i - k + 1 >= 0) {
            result[i - k + 1] = nums[dq.peek()];
        }
    }
    return result;
}

据我了解，此代码的最坏情况复杂度将是 n*k，因为在最坏情况下，内部 while 循环将执行 k 次。然而作者说过摊销时间复杂度是O(n)。那个怎么样 ？我不完全明白？

Answer 1

由于内部 (while) 循环对于外部 (for) 循环的每次迭代都有不同的迭代次数，因此您不能简单地用 k 限制该循环的迭代次数，因为该限制不会足够紧。

相反，我们可以尝试计算内部循环所有迭代的操作总数。

外部循环将每个索引恰好添加到队列一次(在 dq.offer(i) 中)。

添加到队列中的每个索引只能删除一次 - 通过 dq.poll() 或 dq.pollLast()。

由于 while 循环的每次迭代都必须从队列中删除一个元素，因此 while 循环的所有迭代(跨外部 for 循环的所有迭代)都以 n< 为界 (因为删除次数不能超过 n)。因此，while 循环的所有迭代都会为总运行时间贡献 O(n)。

除了 while 循环之外，外层 for 循环内的其他操作显然需要常数时间，因此在添加外层循环的所有迭代时，它们会花费 O(n) 时间。

因此总运行时间为O(n)。