Amazon VO 面试真题解析：Sliding Window Maximum（滑动窗口最大值）

Sliding Window Maximum

Given an array arr[] and an integer K, find the maximum value in every contiguous subarray of size K.

Example:

Input: arr[] = {1, 2, 3, 1, 4, 5}, K = 3
Output: 3 3 4 5

Explanation:

Maximum of 1, 2, 3 is 3
Maximum of 2, 3, 1 is 3
Maximum of 3, 1, 4 is 4
Maximum of 1, 4, 5 is 5

这道题要求在长度为 K 的每个连续子数组中，快速求出最大值并按顺序输出。面试中通常使用单调队列来维护窗口内的候选最大值：队列中保存元素下标，并保证对应值从队首到队尾单调递减；每次窗口右移时，先移除已经滑出窗口的下标，再弹出所有比当前元素更小的下标，最后队首就是当前窗口最大值。这样可以把暴力扫描的 O(nK) 降到 O(n)，非常适合 Amazon 这类高频数组题。