剑指 Offer.59-I.滑动窗口的最大值

题目链接

问题描述

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

个人想法（模拟）

移动窗口每变化一次，对当前窗口的元素进行扫描，返回当前窗口中最大的元素

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0) return new int[0];
        //1. 模拟遍历滑动窗口中的最大值
        //2. 使用一个变量维护最大值 降低复杂度
        int left = 0;
        int right = k-1;
        List<Integer> res = new ArrayList<>();
        // 尝试通过模拟实现
        while(right < nums.length){
            int windowsMax = Integer.MIN_VALUE;
            for(int i = left;i <= right;i++){
                windowsMax = Math.max(windowsMax,nums[i]);
            }
            res.add(windowsMax);
            left++;
            right++;
        }
        int [] resArray = new int[res.size()];
        // 将数值从List中拷贝至数组中
        for(int i=0;i<res.size();i++){
            resArray[i] = res.get(i);
        }
        return resArray;
    }
}

个人想法（递减队列）

在窗口动态变化的过程中，始终维护一个递减队列，当左边界变化时，判断当前最大元素是否为左边界的元素，若是，则将该元素从队首移除

代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0) return new int[0];
        // 改进：通过Deque实现单调队列
        Deque<Integer> deque = new LinkedList<>();
        //1. 模拟遍历滑动窗口中的最大值
        //2. 使用一个变量维护最大值 降低复杂度
        int left = 0;
        int right = k-1;
        List<Integer> res = new ArrayList<>();
        // 尝试通过模拟实现
        
        //首先扫描第一个窗口
        for(int i = left;i <= right;i++){
            while(!deque.isEmpty() && nums[i] > deque.peekLast()){
                //将小于当前最大值的全部出队
                deque.pollLast();
            }
            // 将当前元素入队
            deque.offerLast(nums[i]);
        }
        
        while(right < nums.length){
            // 判断最大值是否为队头元素
            res.add(deque.peekFirst());
            // 将右侧新元素入队
            if(deque.peekFirst().equals(nums[left])){
                deque.pollFirst();
            }
            left++;
            right++;
            if(right<nums.length){
                while(!deque.isEmpty() && nums[right] > deque.peekLast()){
                //将小于当前最大值的全部出队
                deque.pollLast();
            }
                // 将当前元素入队
                deque.offerLast(nums[right]);
            }
        }

        int [] resArray = new int[res.size()];
        // 将数值从List中拷贝至数组中
        for(int i=0;i<res.size();i++){
            resArray[i] = res.get(i);
        }
        return resArray;
    }
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。