package com.fishercoder.solutions;

import java.util.PriorityQueue;

public class _239 {

    public static class Solution1 {
        public int[] maxSlidingWindow(int[] nums, int k) {
            if (nums == null || nums.length == 0 || k == 0) {
                return new int[0];
            }
            PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b - a);
            int[] res = new int[nums.length - k + 1];
            for (int i = 0; i < nums.length; i++) {
                if (i < k) {
                    heap.offer(nums[i]);
                    if (i == k - 1) {
                        res[0] = heap.peek();
                    }
                } else {
                    heap.remove(nums[i - k]);
                    heap.offer(nums[i]);
                    res[i - k + 1] = heap.peek();
                }
            }
            return res;
        }
    }
}

@@ -46,29 +46,26 @@
 va.util.
-PriorityQueue
+LinkedList
 ;%0A%0Apubli
@@ -116,20 +116,16 @@
 tion1 %7B%0A
-    
     publ
@@ -183,53 +183,42 @@
     
-    if (nums == null %7C%7C nums.length == 0 %7C%7C k
+int n = nums.length;%0A        if (n
  == 
@@ -218,28 +218,24 @@
  (n == 0) %7B%0A
-    
             
@@ -246,30 +246,21 @@
 rn n
-ew int%5B0%5D;%0A   
+ums;%0A
         
  %7D%0A 
@@ -247,33 +247,32 @@
 n nums;%0A        
- 
 %7D%0A            Pr
@@ -269,138 +269,96 @@
     
-    PriorityQueue%3CInteger%3E heap = new PriorityQueue%3C%3E((a, b) -%3E b - a);%0A            int%5B%5D res
+int%5B%5D result = new int%5Bn - k + 1%5D;%0A        LinkedList%3CInteger%3E dq
  = new 
+L
 in
-t%5Bnums.length - k + 1%5D;%0A    
+kedList%3C%3E();%0A
     
@@ -382,26 +382,16 @@
 0; i %3C n
-ums.length
 ; i++) %7B
@@ -407,63 +407,78 @@
     
-    if (i %3C k) %7B%0A                    heap.offer(nums%5Bi%5D
+if (!dq.isEmpty() && dq.peek() %3C i - k + 1) %7B%0A                dq.poll(
 );%0A 
@@ -484,32 +484,34 @@
             
+%7D%0A
         
 if (i == k -
@@ -502,71 +502,69 @@
     
-if (i == k - 1) %7B%0A                        res%5B0
+    while (!dq.isEmpty() && nums%5Bi
 %5D 
+%3E
 = 
-heap.peek();
+nums%5Bdq.peekLast()%5D) %7B
 %0A   
@@ -572,34 +572,39 @@
             
-    %7D%0A    
+dq.pollLast();%0A
             
@@ -608,17 +608,9 @@
    %7D
- else %7B%0A 
+%0A
     
@@ -621,86 +621,55 @@
     
-       heap.remove(nums%5Bi - k%5D);%0A                    heap.offer(nums%5Bi%5D);%0A    
+dq.offer(i);%0A            if (i - k + 1 %3E= 0) %7B%0A
     
@@ -683,16 +683,19 @@
      res
+ult
 %5Bi - k +
@@ -704,19 +704,23 @@
 %5D = 
-heap
+nums%5Bdq
 .peek()
+%5D
 ;%0A  
@@ -729,33 +729,26 @@
         
-    %7D%0A   
+%7D%0A
         
  %7D%0A     
@@ -731,39 +731,34 @@
       %7D%0A        
- 
 %7D%0A
-    
         return r
@@ -759,28 +759,25 @@
 turn res
-;%0A   
+ult;%0A
     
- 
 %7D%0A
-  
   %7D%0A%7D%0A

Update _239.java (#77)