?算法，不如说它是一种思考方式?

算法专栏： ??123

一、?239. 滑动窗口最大值

• 题目描述：给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
  返回 滑动窗口中的最大值 。

• 来源：力扣（LeetCode）

• 难度：困难

• 提示：
  1 <= nums.length <= 10⁵
  -10⁴<= nums[i] <= 10⁴
  1 <= k <= nums.length

• 示例 1：
  输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
  输出：[3,3,5,5,6,7]
  解释：
  滑动窗口的位置   最大值
  --------------- -----
  [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
  示例 2：
  输入：nums = [1], k = 1
  输出：[1]

?解题

0.窗口内排序 — 超出时间限制

在给定大小的窗口内选择一个最大值，我们就会想到排序了。
我们依次遍历数组，往集合内添加数组；
当集合大小满足窗口大小条件时就开始从大到小排序，每次集合首个元素就是窗口最大值；
之后遍历数组就是删除集合元素、添加集合元素、排序集合…

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] ans=new int[nums.length-k+1];
        List<Integer> numsList=new LinkedList<>();

        int i = 0;
        for (; i < k; i++) {
            numsList.add(nums[i]);
        }
        for (; i <= nums.length; i++) {
            numsList.sort(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o2-o1;//排序，可以写成lambda表达式
                }
            });

            for (Integer integer : numsList) {
                ans[i-k]=integer;break;//只需要集合第一个（最大值）
            }
            if(i == nums.length)break;//因为最后一个元素的问题~
            numsList.remove((Integer) nums[i-k]);
            numsList.add((Integer) nums[i]);
        }
        return  ans;
    }
}

每次加入集合后额外进行排序消耗大量时间！于是看看自排序的集合能不能好一些。

1.TreeMap的自动排序

TreeSet 也是自排序的，为什么不考虑 TreeSet 呢？会去掉重复的，而 TreeMap 可以通过键值判断删减元素！
思路还是一样的，我们可以改写成类似的。

• code：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] ans=new int[nums.length-k+1];
        Map<Integer,Integer> numsMap=new TreeMap<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });

        int i = 0;
        for (; i < k; i++) {
            if(numsMap.containsKey(nums[i]))
                numsMap.put(nums[i],numsMap.get(nums[i]) + 1);
            else
                numsMap.put(nums[i],1);
        }
        for (; i <= nums.length; i++) {
            for (Integer integer : numsMap.keySet()) {
                ans[i-k]=integer;break;
            }

            if(i == nums.length)break;

            //delete & add
            if(numsMap.get(nums[i-k])>1)
                numsMap.put(nums[i-k],numsMap.get(nums[i-k])-1);
            else
                numsMap.remove(nums[i-k]);

            if(numsMap.containsKey(nums[i]))
                numsMap.put(nums[i], numsMap.get(nums[i])+1);
            else
                numsMap.put(nums[i],1);
        }
        return  ans;
    }
}

可以看到是不超时了，但是时间复杂度仍然好高，有没有可能不排序呢？
 单调队列！

2.单调队列 不排序

对于这个滑动窗口我们其实不需要保留全部的元素，就是说我们每次新加入的元素如果是当前窗口最大的，那么前面的值都是不必要的了！那么进一步看，我们每次新加入的元素如果是比当前窗口末尾元素大，那这个末尾元素也是没有用的，也是可以删除。
我们可以使用一个队列来完成这个窗口：

循环遍历步骤：

1. 重复检查队列首元素是否满足窗口的要求：deque.peek()<i-k+1 则不在窗口内；
2. 重复检查当前队尾元素是否小于当前遍历到的元素：nums[deque.peekLast()]<nums[i] 则删除队尾；保证队列是单调减的。
3. 当前遍历的元素入队；
4. 如果队列满足窗口长度，队首元素为窗口内最大值，输出。

• code：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] ans = new int[nums.length - k + 1];
        ArrayDeque<Integer> deque=new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
            while(!deque.isEmpty() && deque.peek()<i-k+1)
                deque.poll();//队首元素不在窗口内
            while (!deque.isEmpty() && nums[deque.peekLast()]<nums[i])
                deque.pollLast();//队尾元素小  删除队尾元素
            deque.offer(i);//入队
            if(i>=k-1)//窗口
                ans[i-k+1]=nums[deque.peek()];
        }
        return ans;
    }
}

返回第一页。☝

☕物有本末，事有终始，知所先后。?

?☝☝☝☝☝我的CSDN☝☝☝☝☝☝?