|
1 | | -packagecom.fishercoder.solutions; |
2 | | - |
3 | | -importjava.util.PriorityQueue; |
4 | | - |
5 | | -/** |
6 | | - * 239. Sliding Window Maximum |
7 | | - * |
8 | | - * 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. |
9 | | - * You can only see the k numbers in the window. Each time the sliding window moves right by one position. |
10 | | -
|
11 | | - For example: |
12 | | -
|
13 | | - Given nums = [1,3,-1,-3,5,3,6,7], and k = 3. |
14 | | -
|
15 | | - Window position Max |
16 | | - --------------- ----- |
17 | | - [1 3 -1] -3 5 3 6 7 3 |
18 | | - 1 [3 -1 -3] 5 3 6 7 3 |
19 | | - 1 3 [-1 -3 5] 3 6 7 5 |
20 | | - 1 3 -1 [-3 5 3] 6 7 5 |
21 | | - 1 3 -1 -3 [5 3 6] 7 6 |
22 | | - 1 3 -1 -3 5 [3 6 7] 7 |
23 | | - Therefore, return the max sliding window as [3,3,5,5,6,7]. |
24 | | -
|
25 | | - Note: |
26 | | - You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array. |
27 | | -
|
28 | | - Follow up: |
29 | | - Could you solve it in linear time? |
30 | | -
|
31 | | - Hint: |
32 | | - How about using a data structure such as deque (double-ended queue)? |
33 | | - The queue size need not be the same as the window’s size. |
34 | | - Remove redundant elements and the queue should store only elements that need to be considered. |
35 | | - */ |
36 | | -publicclass_239 { |
37 | | - |
38 | | -publicstaticclassSolution1 { |
39 | | -publicint[]maxSlidingWindow(int[]nums,intk) { |
40 | | -if (nums ==null ||nums.length ==0 ||k ==0) { |
41 | | -returnnewint[0]; |
42 | | - } |
43 | | -PriorityQueue<Integer>heap =newPriorityQueue<>((a,b) ->b -a); |
44 | | -int[]res =newint[nums.length -k +1]; |
45 | | -for (inti =0;i <nums.length;i++) { |
46 | | -if (i <k) { |
47 | | -heap.offer(nums[i]); |
48 | | -if (i ==k -1) { |
49 | | -res[0] =heap.peek(); |
50 | | - } |
51 | | - }else { |
52 | | -heap.remove(nums[i -k]); |
53 | | -heap.offer(nums[i]); |
54 | | -res[i -k +1] =heap.peek(); |
55 | | - } |
56 | | - } |
57 | | -returnres; |
58 | | - } |
59 | | - } |
| 1 | +publicclassSolution { |
| 2 | +publicint[]maxSlidingWindow(int[]a,intk) { |
| 3 | +if (a ==null ||k <=0) { |
| 4 | +returnnewint[0]; |
| 5 | +} |
| 6 | +intn =a.length; |
| 7 | +int[]r =newint[n-k+1]; |
| 8 | +intri =0; |
| 9 | +// store index |
| 10 | +Deque<Integer>q =newArrayDeque<>(); |
| 11 | +for (inti =0;i <a.length;i++) { |
| 12 | +// remove numbers out of range k |
| 13 | +while (!q.isEmpty() &&q.peek() <i -k +1) { |
| 14 | +q.poll(); |
| 15 | +} |
| 16 | +// remove smaller numbers in k range as they are useless |
| 17 | +while (!q.isEmpty() &&a[q.peekLast()] <a[i]) { |
| 18 | +q.pollLast(); |
| 19 | +} |
| 20 | +// q contains index... r contains content |
| 21 | +q.offer(i); |
| 22 | +if (i >=k -1) { |
| 23 | +r[ri++] =a[q.peek()]; |
| 24 | +} |
| 25 | +} |
| 26 | +returnr; |
| 27 | +} |
60 | 28 | } |