LeetCode

239. 滑动窗口最大值

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。求滑动窗口中的最大值。

  1. public int[] maxSlidingWindow(int[] nums, int k) {
  2.     if (nums == null || k > nums.length)    return null;
  3.     int n = nums.length;
  4.     int[] res = new int[n-k+1];
  5.     LinkedList<Integer> queue = new LinkedList();
  6.     for (int i = 0; i < n; i++) {
  7.         while(!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]){
  8.             queue.pollLast();
  9.         }
  10.         while (!queue.isEmpty() && queue.peek() + k <= i) {
  11.             queue.poll();
  12.         }
  13.         queue.offer(i);
  14.         if (i >= k-1) {
  15.             res[i-k+1] = nums[queue.peek()];
  16.         }
  17.     }
  18.     return res;
  19. }

采用单调队列，弹出队列中所有小于或等于当前值的元素，并且需要弹出所有不在窗口中的元素，因此需要两个循环（其实第二个循环只需要判断一个元素就行，因为窗口每次移动一格）。
由于所有元素只能入队列一次，因此时间复杂度是O(n)。