【leetcode hot 100 239】滑动窗口最大值

weixin_47894469

310人浏览 · 2025-03-01 22:14:00

weixin_47894469 · 2025-03-01 22:14:00 发布

解法一：循环每个`i`，找`i+k`中的最大值。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] results= new int[nums.length-k+1];
        for(int i=0; i<results.length; i++){
            // int max=0; //不适合负数
            int max=nums[i];
            for(int j=0; j<k; j++){
                max = Math.max(max, nums[i+j]);
            }
            results[i]=max;
        }
        return results;
    }
}

注意：

要多考虑复数的情况

错误原因：超出时间限制

解法二：保存上一个子串的最大值，若新加入的值大于最大值，则更改最大值。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] results= new int[nums.length-k+1];
        // 先计算result[1]
        int max=nums[0], max_i=0;
        for(int j=0; j<k; j++){
            if(max<nums[j]){
                max = nums[j];
                max_i =j;
            }
        }
        results[0]=max;
        for(int i=1; i<results.length; i++){
            if(i<=max_i && max_i<i+k){
                if(max<nums[i+k-1]){
                    max = nums[i+k-1];
                    max_i =i;
                }
            }else{
                max=nums[i];
                max_i=i;
                for(int j=1; j<k; j++){
                    if(max<nums[i+j]){
                        max = nums[i+j];
                        max_i = i+j;
                    }
                }
            }
            results[i]=max;
        }
        return results;
    }
}

错误原因：超出时间限制

方法三：优先队列

对于「最大值」，我们可以想到一种非常合适的数据结构，那就是优先队列（堆），其中的大根堆可以帮助我们实时维护一系列元素中的最大值。

对于本题而言，初始时，我们将数组 nums 的前 k 个元素放入优先队列中。每当我们向右移动窗口时，我们就可以把一个新的元素放入优先队列中，此时堆顶的元素就是堆中所有元素的最大值。然而这个最大值可能并不在滑动窗口中，在这种情况下，这个值在数组 nums 中的位置出现在滑动窗口左边界的左侧。因此，当我们后续继续向右移动窗口时，这个值就永远不可能出现在滑动窗口中了，我们可以将其永久地从优先队列中移除。

我们不断地移除堆顶的元素，直到其确实出现在滑动窗口中。此时，堆顶元素就是滑动窗口中的最大值。为了方便判断堆顶元素与滑动窗口的位置关系，我们可以在优先队列中存储二元组 (num,index)，表示元素 num 在数组中的下标为 index。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] results= new int[nums.length-k+1];
        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});
        }
        results[0]=pq.peek()[0];
        for(int i=1; i+k-1<nums.length; i++){
            pq.offer(new int[]{nums[i+k-1],i+k-1});
            while(pq.peek()[1]<i){ // 使用while，把所有不在范围内的数都删除
                pq.poll();
            }
            results[i]=pq.peek()[0];
        }
        return results;
    }
}

注意：

优先队列的定义：

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];
            }
        });