239.Sliding Window Maximum

tags: Hard Array Queue Sliding Window Heap

239. 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⁵
• -10⁴ <= nums[i] <= 10⁴
• 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;
}

SheepWed, 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
JimAug 16, 2023

Reference

回到題目列表