@@ -0,0 +1,2044 @@
+// 239. Sliding Window Maximum%0A/**%0A * 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.%0A * %0A * For example,%0A * Given nums = %5B1,3,-1,-3,5,3,6,7%5D, and k = 3.%0A * %0A * Window position                Max%0A * ---------------               -----%0A * %5B1  3  -1%5D -3  5  3  6  7       3%0A *  1 %5B3  -1  -3%5D 5  3  6  7       3%0A *  1  3 %5B-1  -3  5%5D 3  6  7       5%0A *  1  3  -1 %5B-3  5  3%5D 6  7       5%0A *  1  3  -1  -3 %5B5  3  6%5D 7       6%0A *  1  3  -1  -3  5 %5B3  6  7%5D      7%0A * Therefore, return the max sliding window as %5B3,3,5,5,6,7%5D.%0A * %0A * Note: %0A * You may assume k is always valid, ie: 1 %3C= k %3C= input array's size for non-empty array.%0A * %0A * Follow up:%0A * Could you solve it in linear time?%0A * %0A * Hint:%0A * 1. How about using a data structure such as deque (double-ended queue)?%0A * 2. The queue size need not be the same as the window's size.%0A * 3. Remove redundant elements and the queue should store only elements that need to be considered.%0A * %0A * Tags: Heap%0A * %0A * Similar Problems: (H) Minimum Window Substring (E) Min Stack (H) Longest Substring with At Most Two Distinct Characters (H) Paint House II%0A * %0A * Author: Xinyue Zhang%0A */%0A%0Apublic class Solution %7B%0A    %0A    public int%5B%5D maxSlidingWindow(int%5B%5D nums, int k) %7B%0A        %0A        if (nums == null %7C%7C k %3C= 0)%0A            return new int%5B0%5D;%0A        %0A        ArrayDeque%3CInteger%3E deque = new ArrayDeque%3CInteger%3E ();%0A        int l = nums.length;%0A        int%5B%5D output = new int%5Bl - k + 1%5D;%0A        %0A        for (int i = 0; i %3C l; i++) %7B%0A            if (!deque.isEmpty() && deque.getFirst() == i - k)%0A                deque.pollFirst();%0A            %0A            while (!deque.isEmpty() && nums%5Bi%5D %3E nums%5Bdeque.getLast()%5D)%0A                deque.pollLast();%0A            %0A            deque.addLast(i);%0A            if (i %3E= k - 1) output%5Bi - k + 1%5D = nums%5Bdeque.getFirst()%5D;%0A        %7D%0A        %0A        return output;%0A    %7D%0A%7D%0A

Create 239_Sliding_Window_Maximum.java