题解 | #滑动窗口的最大值#

import java.util.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型一维数组
     * @param size int整型
     * @return int整型ArrayList
     */
    public static ArrayList<Integer> maxInWindows (int[] num,
            int size) throws InterruptedException {
        // write code here
        if (size > num.length) {
            return new ArrayList<>();
        }

        ArrayList<Integer> list = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0 ; i < num.length; i++) {
            // 获取窗口大小的数组，对数组数据排序，获取其中最大值，并别判断最大值是否是最后一位
            queue.add(num[i]);
            if (queue.size() == size) {
                Object[] array = queue.toArray();
                //    log.info("array:{},size:{}",array,array.length);
                // 创建一个int数组来存储转换后的结果
                int[] intArray = new int[array.length];
                // 遍历Object[]数组，将Integer转换为int并存储到intArray中
                for (int j = 0; j < array.length; j++) {
                    // 强制类型转换，因为我们知道这里只会有Integer对象
                    intArray[j] = (Integer) array[j];
                }
                quickSort(intArray, 0, intArray.length - 1);
                // log.info("排序之后的数组：{},最大值：{}",intArray,intArray[2]);
                //resqueue.put(intArray[2]);
                list.add(intArray[size - 1]);
                //arr[index++] = intArray[2];
                queue.poll();

            }

        }
        return list;
    }

    public static void quickSort(int[] arr, int low, int high) {
        //log.info("arr: {},low:{},high:{}", arr, low, high);
        if (low < high) {
            // 找到划分点
            int pivotIndex = index(arr, low, high);
            //log.info("pivotIndex: {},arr:{}", pivotIndex, arr);

            // 递归地对左右两部分进行快速排序
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }



    private static int index(int[] array, int low, int high) {
        int idx = array[high];
        int i = (low - 1);
        for (int j = low ; j < high ; j++) {
            if (idx >= array[j]) {
                i++;
                // 移动数据，小于基准值的放在最左面
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        // 本次移动之后，将基准值放入左面 i 之后
        int temp = array[i + 1] ;
        array[i + 1] = array[high];
        array[high] = temp;
        return i + 1;
    }

}

思路：应用队列维护一个窗口大小数据，将队列数据转成数组，应用快速排序，从小到大，每次只获取窗口大小-1的数据