|
2 | 2 |
|
3 | 3 | importjava.util.PriorityQueue; |
4 | 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 | 5 | publicclass_239 { |
37 | 6 |
|
38 | 7 | publicstaticclassSolution1 { |
|