Google Intern 新鲜面筋

写了下第一轮的代码，这里使用普通的priorityqueue， 时间复杂度是O(nk)

1. public class MaximumInMinimumInWindowK {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 int[] arr = {3, 2, 5, 2, 9, 3, 7, 6, 5};
   
5.                 System.out.println(getMaximumInMinimumInWindowK(arr, 6));
   
6.         }
   
7.         public static int getMaximumInMinimumInWindowK(int[] arr, int k) {
   
8.                 if (arr == null || arr.length == 0) {
   
9.                         return Integer.MIN_VALUE;
   
10.                 }
    
11.                 int res = Integer.MIN_VALUE;
    
12.                 PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
    
13.                 for (int i = 0; i < arr.length; i++) {
    
14.                         pq.offer(arr[i]);
    
15.                         if (i >= k - 1) {
    
16.                                 res = Math.max(res, pq.peek());
    
17.                                 pq.remove(arr[i - k + 1]);
    
18.                         }
    
19.                 }
    
20. 
    
21.                 return res;
    
22.         }
    
23. }

复制代码

感谢分享

mingzhou1987 发表于 2016-2-26 15:04
第一轮是一个X的window一直向右移找最小值么。。如果用heap的话复杂度貌似是nlogk,不知道可不可以更优

deque可以n找到

有比xor更快的算法。。。？