Sliding Window Maximum

LeetCode Q 239 - Sliding Window Maximum

Given an array 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: Input: nums = [1,3,-1,-3,5,3,6,7], and 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

Note: You may assume k is always valid, 1 ≤ k ≤ input array's size for non-empty array.

Follow up: Could you solve it in linear time?

Solution: Sliding Window

TreeMap<Integer, Integer>: used to count how many times we have meet a number. key: number, value: times.

Code:

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

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

  Map<Integer, Integer> map = new TreeMap<>();
  int[] arr = new int[nums.length];

  int left = 0, right = 0;

  while (right < nums.length) {
    if (right - left + 1 > k) {
      map.put(nums[left], map.get(nums[left]) - 1);
      if (map.get(nums[left]) == 0) map.remove(nums[left]);
      left++;
    }

    map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);

    arr[right++] = map.getLastKey();
  }

  int[] res = new int[nums.length - k + 1];
  int index = 0;
  for (int i = k - 1; i < nums.length; i++) 
    res[index++] = arr[i];

  return res;
}