滑动窗口与堆结合

2023-12-13 06:40:38

1.堆与滑动窗口问题的结合

在《堆》一章解释过堆的大小一般是有限的,而且能直接返回当前位置下的最大值或者最小值。而该特征与滑动窗口结合,碰撞出的火花可以非常方便的解决一些特定场景的问题。
LeetCode239 给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位,返回滑动窗口中的最大值。

输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]
解释:
滑动窗口的位置                最大值
---------------               -----
[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

这种方法我们在基础算法的堆部分介绍过。对于最大值、K个最大这种场景,优先队列(堆)是首先应该考虑的思路。大根堆可以帮助我们实时维护一系列元素中的最大值。
本题初始时,我们将数组 nums 的前 k个元素放入优先队列中。每当我们向右移动窗口时,我们就可以把一个新的元素放入优先队列中,此时堆顶的元素就是堆中所有元素的最大值。然而这个最大值可能并不在滑动窗口中,在这种情况下,这个值在数组 nums 中的位置出现在滑动窗口左边界的左侧。因此,当我们后续继续向右移动窗口时,这个值就永远不可能出现在滑动窗口中了,我们可以将其永久地从优先队列中移除。
我们不断地移除堆顶的元素,直到其确实出现在滑动窗口中。此时,堆顶元素就是滑动窗口中的最大值。为了方便判断堆顶元素与滑动窗口的位置关系,我们可以在优先队列中存储二元组 (num,index),表示元素num 在数组中的下标为index。

public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    PriorityQueue<int[]> pq = new Priority<>(new Comparator<int[]>(){
        public int compare(int[] pair1, int[] pair2) {
            return pair1[0]!=pair2 ? 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;k<n;k++){
        pq.offer(new int[]{nums[i], i});
        while(pq.peek()[1]<=i-k){
            pq.poll();
        }
        ans[i-k+1] = pq.peek()[0];
    }
    return ans;
}

下面是对代码每一句的解释:

  1. int n = nums.length;:获取输入数组nums的长度,并将其存储在变量n中。
  2. PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {...});:创建一个优先队列pq,用于存储整数数组。优先队列中的每个元素都是一个包含两个整数的数组,第一个整数表示数组的值,第二个整数表示该值在原数组中的索引。
  3. for (int i = 0; i < k; ++i) { pq.offer(new int[]{nums[i], i}); }:将数组的前k个元素添加到优先队列中。
  4. int[] ans = new int[n - k + 1];:创建一个长度为n-k+1的整数数组ans,用于存储结果。
  5. ans[0] = pq.peek()[0];:将优先队列中的第一个元素(即当前窗口的最大值)赋值给结果数组的第一个元素。
  6. for (int i = k; i < n; ++i) { ... }:从第k个元素开始遍历数组,直到最后一个元素。
  7. pq.offer(new int[]{nums[i], i});:将当前元素添加到优先队列中。
  8. while (pq.peek()[1] <= i - k) { pq.poll(); }:如果优先队列中的元素索引小于等于当前窗口的起始索引减去k,则将其从优先队列中移除。这样可以确保优先队列中始终包含当前窗口内的元素。
  9. ans[i - k + 1] = pq.peek()[0];:将优先队列中的第一个元素(即当前窗口的最大值)赋值给结果数组的对应位置。
  10. return ans;:返回结果数组。

文章来源:https://blog.csdn.net/m0_53401014/article/details/134895612
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。