滑动窗口最大值

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

java指针：

package Leetcode;
import java.util.Arrays;
import java.util.Scanner;
public class maxSlidingWindow {
    public static int maxvalue(int [] nums)
    {
        int max=nums[0];
        for (int i = 1; i <=nums.length-1 ; i++) {
            if (nums[i]>max)
                max=nums[i];
        }
        return max;
    }
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int len=nums.length;//数组的长度
        int []res;
        if (k>=len)//若长度大于k，则只记录一个最大的值，为数组整体的最大值
        {
            res=new int[1];
            Arrays.sort(nums);
            res[0]=nums[len-1];
        }
        else
        {
            res=new int[len-k+1];//数组长度为1+len-k
            int []temp=new int[k];//用于寻找前k个数的最大值
            for (int i = 0; i <temp.length ; i++) {
                temp[i]=nums[i];
            }
            int begin=0;//开始指针
            int end=k-1;//末尾指针
            int max=maxvalue(temp);//前k个数的最大值
            int i=0;//数组填充指针
            res[i]=max;
            while (end<nums.length-1)
            {
                end++;
                begin++;
               if (nums[end]>=max)//若后一个数大于前面数的最大值，则更新最值
               {
                   res[++i]=nums[end];
                   max=nums[end];
               }
               else if (nums[end]<max&&nums[begin-1]!=max)//若后一个数小于前面数的最大值，且向前移动的数不是最值
               {
                   res[++i]=max;
               }
               else if (nums[end]<max&&nums[begin-1]==max)//若后一个数小于前面数的最大值，且向前移动的数是最值
               {
                   int []temp1=new int[k];
                   int temp2=begin;
                   for (int j = 0; j <k&&temp2<=nums.length-1 ; j++,temp2++) {
                       temp1[j]=nums[temp2];
                   }
                   max=maxvalue(temp1);
                   res[++i]=max;
               }
            }
        }
       return res;
    }
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int len=scanner.nextInt();//数组长度
        int k=scanner.nextInt();//窗口大小
        int []nums=new int[len];
        for (int i = 0; i <len ; i++) {//数组赋值
            nums[i]=scanner.nextInt();
        }
        int []res=maxSlidingWindow(nums,k);
        System.out.println(Arrays.toString(res));
    }
}

运行结果如下

优先队列

package Leetcode;

import java.util.Comparator;
import java.util.PriorityQueue;

public class maxSlidingWindow2 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] pair1, int[] pair2) {
                return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
            }
        });
        for (int i = 0; i < k; ++i) {
            pq.offer(new int[]{nums[i], i});
        }
        int[] ans = new int[n - k + 1];
        ans[0] = pq.peek()[0];
        for (int i = k; i < n; ++i) {
            pq.offer(new int[]{nums[i], i});
            while (pq.peek()[1] <= i - k) {
                pq.poll();
            }
            ans[i - k + 1] = pq.peek()[0];
        }
        return ans;
    }

}

本文地址：https://blog.csdn.net/lianggege88/article/details/112108142