算法之滑动窗口

力扣239

package com.zhang.reflection.面试.算法模版.滑动窗口;
import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;
/**
 * 给你一个整数数组 nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。
 * 你只可以看到在滑动窗口内的 k个数字。滑动窗口每次只向右移动一位。
 *
 * 返回 滑动窗口中的最大值 。
 *
 */
public class 滑动窗口最大值 {
    /**
     * 解法一：使用优先队列
     * 对于「最大值」，我们可以想到一种非常合适的数据结构，那就是优先队列（堆），其中的大根堆可以帮助我们实时维护一系列元素中的最大值。
     *
     * 对于本题而言，初始时，我们将数组 \textit{nums}nums 的前 kk 个元素放入优先队列中。
     * 每当我们向右移动窗口时，我们就可以把一个新的元素放入优先队列中，此时堆顶的元素就是堆中所有元素的最大值。然而这个最大值可能并不在滑动窗口中，
     * 在这种情况下，这个值在数组 \textit{nums}nums 中的位置出现在滑动窗口左边界的左侧。因此，当我们后续继续向右移动窗口时，
     * 这个值就永远不可能出现在滑动窗口中了，我们可以将其永久地从优先队列中移除。
     *
     * 我们不断地移除堆顶的元素，直到其确实出现在滑动窗口中。此时，堆顶元素就是滑动窗口中的最大值。
     * 为了方便判断堆顶元素与滑动窗口的位置关系，我们可以在优先队列中存储二元组 (\textit{num}, \textit{index})(num,index)，
     * 表示元素 \textit{num}num 在数组中的下标为 \textit{index}index。
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        PriorityQueue<int[]> heap=new PriorityQueue<int[]>((a, b)->a[0]==b[0]?b[1]-a[1]:b[0]-a[0]);
        for(int i=0;i<k;i++){
            heap.offer(new int[]{nums[i],i});
        }
        int[] result=new int[nums.length-k+1];
        result[0]=heap.peek()[0];
        for(int i=k;i<nums.length;i++){
            heap.offer(new int[]{nums[i],i});
            while(heap.peek()[1]<=i-k){
                heap.poll();
            }
            result[i-k+1]=heap.peek()[0];
        }
        return result;
    }

    /**
     * 解法二：单调队列
     * https://leetcode-cn.com/problems/sliding-window-maximum/solution/hua-dong-chuang-kou-zui-da-zhi-by-leetco-ki6m/
     */
    public int[] maxSlidingWindow1(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<Integer>();
        for (int i = 0; i < k; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }

        int[] ans = new int[n - k + 1];
        ans[0] = nums[deque.peekFirst()];
        for (int i = k; i < n; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            while (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            ans[i - k + 1] = nums[deque.peekFirst()];
        }
        return ans;
    }
}