239. Sliding Window Maximum.md

239. Sliding Window Maximum

Question

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

Thinking:

• Method 1:优先级队列。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length == 0) return nums;
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>(){
            @Override
            public int compare(Integer n1, Integer n2){
                return n2 - n1;
            }
        });
        for(int i = 0; i < k; i++)
            pq.offer(nums[i]);
        int[] result = new int[nums.length - k + 1];
        for(int i = k; i <= nums.length; i++){
            result[i - k] = pq.peek();
            pq.remove(nums[i - k]);
            if(i < nums.length) pq.offer(nums[i]);
        }
        return result;
    }
}

二刷

1. Still use priority queue. It's not O(n);

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length == 0) return new int[0];
        int len = nums.length;
        int[] result = new int[len - k + 1];
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>(){
            @Override
            public int compare(Integer a, Integer b){
                return b - a;
            }
        });
        for(int i = 0; i < k; i++){
            pq.offer(nums[i]);
        }
        for(int i = k; i <= nums.length; i++){
            result[i - k] = pq.peek();
            pq.remove(nums[i - k]);
            if(i < nums.length)
                pq.offer(nums[i]);
        }
        return result;
    }
}

2. We can use Deque for this question. In deque, we only save the index of each number.

• For each index, we check if the peek is the one leaving the window, if so, remove it.
• Then we check from the end of the deque, remove the numbers that are smaller than the current one.
• Then we can add the number corresponding to peek index to our result for current position.

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];
        LinkedList<Integer> deque = new LinkedList<>();
        for(int i = 0; i < nums.length; i++){
            if(!deque.isEmpty() && deque.peek() == i - k) deque.poll();
            while(!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) deque.pollLast();
            deque.offer(i);
            if(i >= k - 1) result[i - k + 1] = nums[deque.peek()];
        }
        return result;
    }
}

Third Time

• Method 1: Deque

  class Solution {
      public int[] maxSlidingWindow(int[] nums, int k) {
          if(nums == null || nums.length == 0) return new int[0];
          LinkedList<Integer> list = new LinkedList<>();
          int[] res = new int[nums.length - k + 1];
          for(int i = 0; i < nums.length; i++){
              while(!list.isEmpty() && nums[i] >= nums[list.getLast()]){
                  list.pollLast();
              }
              list.add(i);
              if(list.get(0) < i - k + 1)
                  list.pollFirst();
              if(i >= k - 1) res[i - k + 1] = nums[list.get(0)];
          }
          return res;
      }
  }

Amazon Session

• Method 1: Deque

   class Solution {
   	public int[] maxSlidingWindow(int[] nums, int k) {
   		if(nums.length < k || nums.length == 0) return new int[0];
   		int[] result = new int[nums.length - k + 1];
   		Deque<Integer> deque = new ArrayDeque<>();
   		int i = 0, index = 0;
   		for(i = 0; i < nums.length; i++){
   			if(i - k >= 0 && !deque.isEmpty() && deque.peek() == i - k) deque.pollFirst();
   			int add = nums[i];
   			while(!deque.isEmpty() && add >= nums[deque.getLast()]){
   				deque.pollLast();
   			}
   			deque.addLast(i);
   			if(i - k + 1 >= 0) result[index++] = nums[deque.getFirst()];
   		}
   		return result;
   	}
   }