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

package org.example.test;

import com.alibaba.fastjson.JSONObject;

import java.util.ArrayList;

public class MaxInWindowsTest {
    public static void main(String[] args) {
        int[] test = {1, 3, 5, 7, 9, 11, 13, 15};
        System.out.println(JSONObject.toJSONString(maxInWindows(test, 4)));
    }

    /**
     * 提示我使用堆和双指正，就写成这样了
     *
     * @param num
     * @param size
     * @return
     */
    public static ArrayList<Integer> maxInWindows(int[] num, int size) {
        if (size == 0) {
            return null;
        }
        ArrayList<Integer> ans = new ArrayList<>();
        int[] heap = new int[size + 1];
        for (int i = 0; i < size; i++) {
            heap[i + 1] = num[i];
        }
        for (int i = size / 2; i > 0; i--) {
            adjustHead(heap, i, size);
        }
        ans.add(heap[1]);
        for (int i = size; i < num.length; i++) {
            int m = 0;
            for (int n = 1; n < heap.length; n++) {
                if (heap[n] == num[i - size]) {
                    m = n;
                    break;
                }
            }
            heap[m] = num[i];
            for (int j = size / 2; j > 0; j--) {
                adjustHead(heap, j, size);
            }
            int k = heap[1];
            ans.add(k);
        }
        return ans;
    }

    private static void adjustHead(int[] num, int i, int size) {
        int tmp = num[i];
        for (int j = i * 2; j <= size; j *= 2) {
            if (j < size && num[j] < num[j + 1]) {
                j++;
            }
            if (num[j] < tmp) {
                break;
            } else {
                num[i] = num[j];
                i = j;
            }
        }
        num[i] = tmp;
    }

     /**
     * 这是类似参考答案
     *
     * @param nums
     * @param k
     * @return
     */
    public static 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) { // 当i到k之间的距离超过heap根节点的index下标的值，说明heap首节点超出范围，需要移掉。
                pq.poll();                  // 始终让最大值保持在k范围内。
            }
            ans[i - k + 1] = pq.peek()[0];
        }
        return ans;
    }

}