大根堆（队列）的使用---滑动窗口最大值_new priorityqueue(new comparator()

大根堆的使用

大根堆的定义是这样的

PriorityQueue<int[]> pq = new PriorityQueue<int[]>(
new Comparator<int[]>() {
	public int compare(int[] cp1, int[] cp2) {
	return cp1[0] == cp2[0] ? cp2[1] - cp1[1] : cp2[0] - cp1[0];
}
	});
1
2
3
4
5
6

这里先是判定数组角标0的位置是否相同，如果不相同就按照数组角标0的数据降序排序，否则按照数组角标1的数据降序排序。

如果不是数组，而是单独的Integer，那么大根堆的定义是这样的

        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
1
2
3
4
5
6

小根堆

这里也一并附上小根堆的写法把，其实就是比较方法降序变成升序而已

        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
1
2
3
4
5
6

PriorityQueue<int[]> pq = new PriorityQueue<>(
new Comparator<int[]>(){
	public int compare(int[] cp1, int[] cp2) {
	return cp1[0] == cp2[0] ? cp1[1] - cp2[1] : cp1[0] - cp2[0];
	}
});
1
2
3
4
5
6

滑动窗口最大值

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

返回滑动窗口中的最大值。

示例 1：

输入：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

示例 2：

输入：nums = [1], k = 1
输出：[1]

示例 3：

输入：nums = [1,-1], k = 1
输出：[1,-1]

示例 4：

输入：nums = [9,11], k = 2
输出：[11]

示例 5：

输入：nums = [4,-2], k = 2
输出：[4]

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length
1
2
3

思路

这题可以用大根堆来做，大根堆会让较大的元素始终在上面，所以我们可以往大根堆里存放数组，里面放有大小和角标。然后我们滑动窗口移动的时候每次都往大根堆里添加数据，然后取出堆顶数据即可。此外，取出数据的时候要根据角标来判断取出的数据是不是在滑动窗口内的。

代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            public int compare(int[] par1,int[] par2) {
                return par1[0] == par2[0] ? par2[1] - par1[1] : par2[0] - par1[0];
            }
        });

        for (int i = 0; i < k; i++) {
            pq.offer(new int[]{nums[i], i});
        }
        int[] ans = new int[nums.length - k + 1];
        ans[0] = pq.peek()[0];

        for (int i = k; i < nums.length; i++) {
            pq.offer(new int[]{nums[i], i});
            while (pq.peek()[1] < i - k + 1) {
                pq.poll();
            }
            ans[i - k + 1] = pq.peek()[0];
        }
        return ans;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sliding-window-maximum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。