Maximum Drawdown in a Sliding Window
Given an array of prices `prices` of length $n$ and a window size $k$, compute the maximum drawdown within each sliding window of size $k$.
The **maximum drawdown** within a window is the largest peak-to-trough decline: $\max_{i \le j}(\text{prices}[i] - \text{prices}[j])$ where $i$ and $j$ are indices within the window and $i \le j$ (the peak must come before the trough).
**Constraints:**
-
\le k \le n \le 10^5$
- $0 \le \text{prices}[i] \le 10^6$
**Example 1:**
- Input: `prices = [10, 8, 12, 7, 11, 9, 6]`, `k = 4`
- Output: `[5, 5, 5, 5]`
- Explanation: Windows are `[10,8,12,7]` (max drawdown 10-7=3? No: 12-7=5), `[8,12,7,11]` (12-7=5), `[12,7,11,9]` (12-7=5), `[7,11,9,6]` (11-6=5).
**Example 2:**
- Input: `prices = [1, 2, 3, 4, 5]`, `k = 3`
- Output: `[0, 0, 0]`
- Explanation: Prices are strictly increasing, so no drawdown in any window.
Provide a solution with better than $O(nk)$ time complexity if possible.
Open the full interactive solver, hints, and worked solution →