滑动窗口的最大值

题目描述

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组 {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]}。

思路一

import java.util.ArrayList;
public class Solution {public ArrayList<Integer> maxInWindows(int [] num, int size){ArrayList<Integer> list = new ArrayList<>();
        if(num == null || num.length == 0 || size == 0)return list;
       
        for(int i = 0; i < num.length - size + 1; i++){int tempMax = num[i];
            for(int j = 1;j < size;j++){if(num[i+j] > tempMax) tempMax = num[i+j];
            }
            list.add(tempMax);

        }
        return list;

    }
}

时间复杂度：O(kn)，k 为滑动窗口的大小，n 为数组的长度

思路二

使用一个双端队列保存有可能成为窗口最大值的数据

这里之所以采用双端队列是因为，当即将进入窗口的数据大于队列中的值，那么队列中的值会依次从尾部进行删除，如果队列头部的数字已经滑出窗口，那么也需要将队列的头部删除，所以我们需要在队列的头部和尾部都进行删除操作，所以需要一个双端队列

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
public class Solution {public ArrayList<Integer> maxInWindows(int [] num, int size)
    {ArrayList<Integer> windowMax = new ArrayList<>();
        // 条件检查
        if (num == null || size < 1 || num.length < 1|| size > num.length) {return windowMax;}
        Deque<Integer> indexQueue = new LinkedList<>();
        /**
         *         窗口还没有被填满时，找最大值的索引
         */
        for (int i = 0; i < size && i < num.length; i++) {
            // 如果索引对应的值比之前存储的索引值对应的值大或者相等，就删除之前存储的值
            while (!indexQueue.isEmpty() && num[i] >= num[indexQueue.getLast()]) {indexQueue.removeLast();
            }
            //  添加索引
            indexQueue.addLast(i);
        }
        // 窗口已经被填满了
        for (int i = size; i < num.length; i++) {
            // 第一个窗口的最大值保存
            windowMax.add(num[indexQueue.getFirst()]);
            // 如果新加入窗口的的值比队列中的值大，就删除队列的值
            while (!indexQueue.isEmpty() && num[i] >= num[indexQueue.getLast()]) {indexQueue.removeLast();
            }
            // 删除队列中已经滑出窗口的数据对应的下标
            if (!indexQueue.isEmpty() && indexQueue.getFirst() <= (i - size)) {indexQueue.removeFirst();
            }
            // 可能的最大的下标索引入队
            indexQueue.addLast(i);
        }
        // 最后一个窗口最大值入队
        windowMax.add(num[indexQueue.getFirst()]);
        return windowMax;
    }
}