求数组最后n个元素最大值（或最小值）的高效增量算法技术问询

Hey there! Great question—this is exactly the kind of problem that sliding window algorithms with deques are designed to solve, and we can extend it to meet your requirement of having the result available for every element in the array. Let’s walk through how this works, step by step.

Core Approach: Deque-Based Sliding Window with History Tracking #

The key idea is to use a double-ended queue (deque) to keep track of candidate indices for the maximum (or minimum) in the sliding window of size n, while maintaining a history array that stores the computed maximum for every position in the original array. This gives us amortized O(1) time per element insertion, and O(1) time to query the maximum for any element's last n elements.

Step 1: Data Structures Needed #

• original_array: Stores the actual values of elements as they are added.
• max_history: An array where max_history[i] holds the maximum value of the last n elements ending at index i (i.e., the window from max(0, i - n + 1) to i).
• max_deque: A deque that stores indices of elements in original_array, ordered such that their corresponding values are in decreasing order. This ensures the front of the deque is always the index of the maximum element in the current window.

Step 2: Inserting a New Element (Incremental Update) #

When adding a new element at index current_idx:

1. Clean up the deque from the tail: Remove all indices from the end of the deque where the corresponding element value is less than or equal to the new element. This is because those elements can no longer be the maximum in any future window that includes the new element.
2. Add the current index to the deque: Append current_idx to the deque.
3. Clean up the deque from the head: Remove any indices from the front of the deque that are outside the current window (i.e., index <= current_idx - n). These elements are no longer part of the last n elements.
4. Record the current maximum: The front of the deque is the index of the maximum element in the current window. Store original_array[max_deque[0]] in max_history[current_idx].

For minimum values, reverse the comparison in step 1 (remove elements greater than or equal to the new element) and maintain the deque in increasing order.

Step 3: Querying the Maximum for Any Element #

To get the maximum of the last n elements ending at index i, simply look up max_history[i]—this is an O(1) operation.

Example Walkthrough (Max Calculation, n=3) #

Let’s say we add elements [4, 2, 5, 3, 7] one by one:

• After adding 4: max_deque = [0], max_history = [4]
• After adding 2: max_deque = [0, 1], max_history = [4,4]
• After adding 5: Remove indices 1 and 0 from deque (since 2 ≤ 5, 4 ≤ 5), add 2. max_deque = [2], max_history = [4,4,5]
• After adding 3: 3 ≤ 5, add 3. Check head: 2 > 3-3=0, so keep. max_deque = [2,3], max_history = [4,4,5,5]
• After adding 7: Remove indices 3 and 2 (3 ≤7,5 ≤7), add 4. max_deque=[4], max_history=[4,4,5,5,7]

Now, if we query index 3 (element 3), max_history[3] gives 5—the max of [2,5,3]. Perfect.

Why This Meets Your Requirements #

• Efficiency: Insertion is amortized O(1) (each element is added/removed from the deque at most once), which is far better than O(n) per insertion. Querying is strictly O(1).
• Incremental: The algorithm updates all necessary structures as each new element is added, no need to recompute from scratch.
• Per-element availability: The max_history array stores the result for every position, so you can get the max of the last n elements ending at any element in O(1) time.
• Auxiliary data: We’re using two auxiliary structures (max_history array and max_deque), which aligns with your allowance for per-element or global辅助数据.

Edge Cases to Consider #

• If the number of elements added so far is less than n: The window includes all elements added up to that point, so the max is the largest element in the array up to that index (the deque handles this automatically, since we don’t remove elements from the head until the window exceeds size n).
• If n=1: The max for each element is the element itself, which the algorithm will correctly record.

内容的提问来源于stack exchange，提问作者barneypitt