[每日一道小算法（七十二）][数组] 滑动窗口的最大值（剑指offer）

川长思鸟来 2023-07-08 02:48 45阅读 0赞

前言：  
每一天，都不要耍赖，不要懈怠，都要给自己一个交代。记得要做有意义的事，让自己有充实感，收获感。

### 题目描述 ###

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组\{2,3,4,2,6,2,5,1\}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为\{4,4,6,6,6,5\}； 针对数组\{2,3,4,2,6,2,5,1\}的滑动窗口有以下6个： \{\[2,3,4\],2,6,2,5,1\}， \{2,\[3,4,2\],6,2,5,1\}， \{2,3,\[4,2,6\],2,5,1\}， \{2,3,4,\[2,6,2\],5,1\}， \{2,3,4,2,\[6,2,5\],1\}， \{2,3,4,2,6,\[2,5,1\]\}。

### 解题思路 ###

这道题逻辑还是很简单的。就看你怎么存储这个最大值了。这里我采用的最大堆来做辅助。先将滑动窗口大小的数据放入到最大堆中。然后进行滑动。最大堆每次删除最左边的值。得出每个窗口的最大值。并将最新的数据放入最大堆中。

### 代码样例 ###

package com.asong.leetcode.maxInWindows;
    
    import java.util.ArrayList;
    import java.util.Comparator;
    import java.util.PriorityQueue;
    
    /** * 滑动窗口的最大值 * 给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3， * 那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： * {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， * {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。 */
    public class Solution { 
    
        public ArrayList<Integer> maxInWindows(int [] num, int size)
        { 
            ArrayList<Integer> result = new ArrayList<Integer>();
    
            if(num==null||num.length==0||size>num.length||size<=0)
            { 
                return result;
            }
            //使用大顶堆实现
            PriorityQueue<Integer> queue = new PriorityQueue<Integer>(size, new Comparator<Integer>() { 
                @Override
                public int compare(Integer o1, Integer o2) { 
                    return o2.compareTo(o1);
                }
            });
            //定义两个指针 滑动窗口的左右指针。
            int right = 0; //右指针
            for (; right < size; right++) { 
                queue.add(num[right]);
            }
            while (right<num.length)
            { 
                result.add(queue.peek());
                queue.remove(num[right-size]);
                queue.add(num[right]);
                right++;
            }
            //最后一次入堆没有保存结果 所以需要在加入一次
            result.add(queue.peek());
            return result;
        }
    }