Implement sliding window maximum (using a deque)?

public int[] MaxSlidingWindow(int[] nums, int k) {

if (nums == null || k <= 0) return new int[0];

int n = nums.Length;

int[] result = new int[n - k + 1];

LinkedList<int> deque = new LinkedList<int>(); // store indices

for (int i = 0; i < n; i++) {

// Remove indices out of window

if (deque.Count > 0 && deque.First.Value <= i - k)

Follow on:

deque.RemoveFirst();

// Remove smaller values from the back

while (deque.Count > 0 && nums[deque.Last.Value] < nums[i])

deque.RemoveLast();

deque.AddLast(i);

if (i >= k - 1)

result[i - k + 1] = nums[deque.First.Value];

return result;

Explanation:

Use a deque to keep indexes of useful elements in current window, ensuring the front is

always max.