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

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

返回滑动窗口中的最大值。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3

滑动窗口的位置                最大值---------------               -----[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

输入：nums = [1,-1], k = 1

输入：nums = [9,11], k = 2

输入：nums = [4,-2], k = 2

提示：

1 <= nums.length <= 105

答案：

class Solution {
       public int[] maxSlidingWindow(int[] nums, int k) {
   //优先队列中存的是数组，包括nums的值和该值的下标。    //只要保证最大值的下标在滑动窗口中，该值就是滑动窗口中的最大值，如果不在，则出队至最大值在滑动窗口内。        int n = nums.length;        if(n == 0 || k == 0 || n == 1) return nums;        int[] num = new int[n - k + 1];        Queue
   
     queue = new PriorityQueue
    
     (new Comparator
     
      (){
               @Override            public int compare(int[] o1, int[] o2){
   //降序排列，如果相同，则下标大的在前面                return o1[0] != o2[0] ? o2[0] - o1[0] : o2[1] - o1[1];            }        });        for(int i = 0; i < k; i++){
               queue.add(new int[]{
   nums[i], i});        }        num[0] = queue.peek()[0];        for(int i = k; i < n; i++){
               queue.add(new int[]{
   nums[i], i});            while (queue.peek()[1] <= i - k) {
   //最大值的下标小于滑动窗口的最小下标，则出队                queue.poll();            }            num[i - k + 1] = queue.peek()[0];        }        return num;    }}
     
    
   

解法二：双端队列

//使用滑动窗口,从队列右边入队//左边最大元素出队，右边小于最大元素的元素出队略

转载地址：https://darkness.blog.csdn.net/article/details/115658943 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！