[leetcode]239. Sliding Window Maximum滑动窗口最大值

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

 1 class Solution {
 2     public int[] maxSlidingWindow(int[] a, int k) {
 3         // corner case
 4         if(k return new int[]{};
 5         //TreeMap要求其key必须可比较大小
 6         TreeMap map = new TreeMap((o1,o2) -> o1 - o2);
 7         int[] result = new int[a.length - k + 1];
 8         
 9         for(int i = 0; i ){
10             // 1. add to bst
11             if(map.containsKey(a[i])){
12                 map.put(a[i], map.get(a[i]) + 1 );
13             }else{
14                 map.put(a[i], 1);
15             }         
16             // 2. remove from bst when window sliding
17             if( i >= k){
18                 map.put(a[i - k] , map.get(a[i - k]) - 1 );
19                 if(map.get(a[i - k]) == 0 ){
20                     map.remove(a[i - k]);
21                 }
22             }            
23             // 3. get max
24             if( i + 1 >= k){
25                 result[ i - (k - 1)] = map.lastKey();
26             }           
27         }
28         return result;       
29     }