Sliding Window Maximum

Decription

https://leetcode.com/problems/sliding-window-maximum/description/

Solution

Quite straightforward, use a heap to maitain the maxium and minium dynamically.

import java.util.*;
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0){
            int[] ret = new int[0];
            return ret;
        }
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        for(int i = 0; i < k; i++) heap.add(nums[i]);
        int[] ret = new int[nums.length - k + 1];
        for (int newIndex = k; newIndex < nums.length; newIndex++){
            ret[newIndex - k] = heap.peek();
            heap.remove(nums[newIndex - k]);
            heap.offer(nums[newIndex]);
        }
        ret[nums.length - k] = heap.peek();
        return ret;
    }
}