本文共 3590 字，大约阅读时间需要 11 分钟。

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. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Example:

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

我的想法

因为这道题不关注index只关注大小，所以用TreeSet。

时间复杂度应该是nlogn？

class Solution {
       public int[] maxSlidingWindow(int[] nums, int k) {
           if(nums == null || k <= 0) return new int[0];                TreeMap
   
     tree = new TreeMap<>();        int[] res = new int[nums.length-k+1];        int curK = 0, index = 0;                for(int i = 0; i < nums.length; i++){
               if(curK < k) {
                   if(tree.containsKey(nums[i])) tree.put(nums[i], tree.get(nums[i])+1);                else tree.put(nums[i], 1);                curK++;            }            if(curK >= k){
                   res[index++] = tree.lastKey();                if(tree.get(nums[i-(k-1)]) > 1) tree.put(nums[i-(k-1)], tree.get(nums[i-(k-1)])-1);                else tree.remove(nums[i-(k-1)]);                curK--;            }        }        return res;    }}
   

解答

jiuzhang solution 1: Monotone queue

用单调队列来解决问题，一般都是需要得到当前的某个范围内的最小值或最大值。

public class Solution {
       void inQueue(Deque
   
     deque, int num) {
           while (!deque.isEmpty() && deque.peekLast() < num) {
               deque.pollLast();        }        deque.offer(num);    }        void outQueue(Deque
    
      deque, int num) {
           if (deque.peekFirst() == num) {
               deque.pollFirst();        }    }        public int[] maxSlidingWindow(int[] nums, int k) {
           if (nums == null || nums.length == 0) {
               return new int[0];        }		int[] res = new int[nums.length-k+1];        		int count = 0;        Deque
     
       deque = new ArrayDeque
      
       ();        for (int i = 0; i < k - 1; i++) {
               inQueue(deque, nums[i]);        }                for(int i = k - 1; i < nums.length; i++) {
               inQueue(deque, nums[i]);            res[count++] = deque.peekFirst();            outQueue(deque, nums[i - k + 1]);        }        return res;    }}
      
     
    
   

leetcode solution 2:

方法和有点相似

A = [2,1,3,4,6,3,8,9,10,12,56], w=4

按照步长分割

2, 1, 3, 4 | 6, 3, 8, 9 | 10, 12, 56|

从左到右找记录每个区间的max

left_max[] = 2, 2, 3, 4 | 6, 6, 8, 9 | 10, 12, 56

从右往左记录max

right_max[] = 4, 4, 4, 4 | 9, 9, 9, 9 | 56, 56, 56

sliding-max(i) = max{right_max(i), left_max(i+w-1)}

sliding_max = 4, 6, 6, 8, 9, 10, 12, 56

class Solution {
       public int[] maxSlidingWindow(int[] nums, int k) {
           if(nums == null || k <= 0) return new int[0];                final int[] max_left = new int[nums.length];        final int[] max_right = new int[nums.length];        max_left[0] = nums[0];        max_right[nums.length - 1] = nums[nums.length - 1];        for (int i = 1; i < nums.length; i++) {
               max_left[i] = (i % k == 0) ? nums[i] : Math.max(max_left[i - 1], nums[i]);            final int j = nums.length - i - 1;            max_right[j] = (j % k == 0) ? nums[j] : Math.max(max_right[j + 1], nums[j]);        }        final int[] sliding_max = new int[nums.length - k + 1];        for (int i = 0, j = 0; i + k <= nums.length; i++) {
               sliding_max[j++] = Math.max(max_right[i], max_left[i + k - 1]);        }        return sliding_max;    }}

转载地址：http://jbqvb.baihongyu.com/