621. Sliding Window Maximum (Monotonic Deque)

Given an array nums and a window size k, return the maximum of each contiguous window of size k as it slides from left to right, using a monotonic deque for O(n) time. The input is JSON {nums, k}.

Input: JSON {nums, k}.

Output: Array — the maximum of each window.

Examples

Input: {"nums":[1,3,-1,-3,5,3,6,7],"k":3}
Output: [3,3,5,5,6,7]
Explanation: Maximum of each size-3 window.

Input: {"nums":[1],"k":1}
Output: [1]
Explanation: One window.

Input: {"nums":[9,8,7],"k":2}
Output: [9,8]
Explanation: Decreasing values.

Constraints

• 1<=k<=n<=10^5

Asked by