239.Sliding Window Maximum
===

###### tags: `Hard` `Array` `Queue` `Sliding Window` `Heap`

[239. Sliding Window Maximum](https://leetcode.com/problems/sliding-window-maximum/)

### 題目描述

You are given an array of integers `nums`, there is a sliding window of size `k` which is moving from the very left of the array to the very right. You can only see the `k` numbers in the window. Each time the sliding window moves right by one position.

Return *the max sliding window.*

### 範例

**Example 1:**

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation: 
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

**Example 2:**

Input: nums = [1], k = 1
Output: [1]

**Constraints**:

* 1 <= `nums.length` <= 10^5^
* -10^4^ <= `nums[i]` <= 10^4^
* 1 <= `k` <= `nums.length`

### 解答

#### TypeScript

思路：
1. 建立一個 deque 用來存放目前 window 範圍內的元素 index，並且 deque 中的索引值對應的元素值是降序排列。
2. 開始遍歷 nums，對目前元素 `nums[i]` 做以下處理：
- 檢查 deque 中的第一個元素是否已經超出 window 範圍，如果是的話就將其移除。
- 從 deque 的尾部移除所有小於 `nums[i]` 的元素索引。這保證了 deque 中的索引值對應的元素值是降序排列。
- 將 `nums[i]` 的索引值放入 deque 的尾部。
- 如果 window 範圍內的元素個數已經達到 k 個，開始將 deque 中的第一個元素對應的元素值放入 result 中。
3. 回傳 result。

function maxSlidingWindow(nums: number[], k: number): number[] {
  const result: number[] = [];
  const deque: number[] = [];

  for (let i = 0; i < nums.length; i++) {
    if (deque.length > 0 && deque[0] < i - k + 1) {
      deque.shift();
    }

    while (deque.length > 0 && nums[deque[deque.length - 1]] < nums[i]) {
      deque.pop();
    }

    deque.push(i);

    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }

  return result;
}

> [name=Sheep][time=Wed, 16 Aug 2023]

#### C#

public class Solution {
    public int[] MaxSlidingWindow(int[] nums, int k) {
        int[] ans = new int[nums.Length - k + 1];
        var deque = new Deque(k);

        for (int i = 0; i < nums.Length; i++) {
            if (deque.PeekFirst() == i - k) {
                deque.RemoveFirst();
            }
            
            while (!deque.IsEmpty() && nums[deque.PeekLast()] < nums[i]) {
                deque.RemoveLast();
            }
            deque.AddLast(i);

            if (i - k + 1 >= 0) {
                ans[i - k + 1] = nums[deque.PeekFirst()];
            }
        }

        return ans;
    }

    class Deque {
        private int[] deque;
        private int head, tail, size;

        public Deque(int size) {
            deque = new int[size];
        }

        public bool IsEmpty() => size == 0;
        public int PeekFirst() => deque[head];
        public int PeekLast() => deque[tail - 1 < 0 ? deque.Length - 1  : tail - 1];
        
        public void AddLast(int value) {
            deque[tail] = value;
            MoveNext(ref tail);
            size++;
        }

        public void RemoveFirst() {
            MoveNext(ref head);
            size--;
        }

        public void RemoveLast() {
            MovePrevious(ref tail);
            size--;
        }

        private void MoveNext(ref int index) {
            index++;
            index = index == deque.Length ? 0 : index;
        }

        private void MovePrevious(ref int index) {
            index--;
            index = index < 0 ? deque.Length - 1 : index;
        }
    }
}

> 原本用 heap 寫，但 heap 移除指定資料沒有比較快，看說明用 deque 就好
> C# 沒有 deque, 也可以用 LinkedList 替代，這邊寫一個堪用、不安全的 deque
> [name=Jim][time=Aug 16, 2023]

### Reference

[回到題目列表](https://marsgoat.github.io/XNnote/coding/leetcodeEveryDay.html)