239. Sliding Window Maximum

Version I - heap - O(n*k)

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) return new int[0];
        int[] result = new int[nums.length - k + 1];

        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(new Comparator<Integer>(){
            public int compare(Integer a, Integer b) {
                return Integer.compare(b, a);
            }
        });

        for (int i = 0; i < k; ++i) {
            pq.offer(nums[i]);
        }

        result[0] = pq.peek();
        for (int i = k; i < nums.length; ++i) {
            pq.remove(nums[i - k]);
            pq.offer(nums[i]);
            result[i - k + 1] = pq.peek();
        }


        return result;
    }
}

Version II - heap + hashTable

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) return new int[0];
        int[] result = new int[nums.length - k + 1];

        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(new Comparator<Integer>(){
            public int compare(Integer a, Integer b) {
                return Integer.compare(b, a);
            }
        });

        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < k; ++i) {
            pq.offer(nums[i]);
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], 0);
            }
            map.put(nums[i], map.get(nums[i]) + 1);
        }

        result[0] = pq.peek();
        for (int i = k; i < nums.length; ++i) {
            if (map.get(nums[i - k]) == 1) {
                map.remove(nums[i - k]);
            } else {
                map.put(nums[i - k], map.get(nums[i - k]) - 1);
            }

            while (!pq.isEmpty() && !map.containsKey(pq.peek())) {
                pq.remove();
            }

            pq.offer(nums[i]);
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], 0);
            }
            map.put(nums[i], map.get(nums[i]) + 1);

            result[i - k + 1] = pq.peek();
        }


        return result;
    }
}

Version III - 1 Deque + 1 queue

if I save nums[i] into deque

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) return new int[0];
        int[] result = new int[nums.length - k + 1];

        Deque<Integer> maxQueue = new ArrayDeque<>();
        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < nums.length; ++i) {
            //check the size and remove if size == k
            if (queue.size() == k) {
                int n = queue.poll();
                if (!maxQueue.isEmpty() && n == maxQueue.peek()) {
                    maxQueue.poll();
                }
            }

            //update maxQueue
            while (!maxQueue.isEmpty() && maxQueue.peekLast() < nums[i]) {
                maxQueue.pollLast();
            }

            //add
            queue.offer(nums[i]);
            maxQueue.offer(nums[i]);

            //what's the max?
            if (queue.size() == k) {
                result[i - k + 1] = maxQueue.peek();
            }
        }


        return result;
    }
}

Version IV - 1 Deque

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) return new int[0];
        int[] result = new int[nums.length - k + 1];

        Deque<Integer> queue = new ArrayDeque<>();

        for (int i = 0; i < nums.length; ++i) {
            //check the size and remove if size == k
            if (!queue.isEmpty() && queue.peek() < i - k + 1) {
                queue.poll();
            }

            //update maxQueue
            while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i]) {
                queue.pollLast();
            }

            //add
            queue.offer(i);

            //what's the max?
            if (i >= k - 1) {
                result[i - k + 1] = nums[queue.peek()];
            }
        }


        return result;
    }
}