剑指offer-题65：滑动窗口的最大值

短命女 2022-05-26 04:11 143阅读 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\]\}。

实验平台：[牛客网][Link 1]

--------------------

## **解决思路：** ##

![这里写图片描述][70]  
![这里写图片描述][70 1]  
![这里写图片描述][70 2]  
![这里写图片描述][70 3]  
流程可以结合表8.4分析。java中ArrayList继承了Deque（即双端队列），可以在队首和队尾进行操作。代码如下

java:

import java.util.ArrayList;
    import java.util.LinkedList;
    
    public class Solution { 
        public ArrayList<Integer> maxInWindows(int[] num, int size) {
            ArrayList<Integer> maxList = new ArrayList<Integer>();
            if (num.length >= size && size >= 1) {
                LinkedList<Integer> indexQueue = new LinkedList<Integer>();
                for (int i = 0; i < size; i++) {
                    while (!indexQueue.isEmpty() && num[i] >= num[indexQueue.getLast()]) {
                        indexQueue.pollLast();
                    }
                    indexQueue.offerLast(i);
                }
                for (int i = size; i < num.length; i++) {
                    maxList.add(num[indexQueue.getFirst()]);
                    while (!indexQueue.isEmpty() && num[i] >= num[indexQueue.getLast()]) {
                        indexQueue.pollLast();
                    }
                    if (!indexQueue.isEmpty() && indexQueue.getFirst() <= i - size) {
                        indexQueue.pollFirst();
                    }
                    indexQueue.offerLast(i);
                }
                maxList.add(num[indexQueue.getFirst()]);
            }
            return maxList;
        }
    }

python:

略

[Link 1]: https://www.nowcoder.com/ta/coding-interviews?page=1
[70]: /images/20220526/0b3e6deabbad417bb470361a1a690337.png
[70 1]: /images/20220526/0959f99a3b0f43ac961e2b71e8132e06.png
[70 2]: /images/20220526/14b4469639994d79ac58c14dfef07b3e.png
[70 3]: /images/20220526/8a8fc2eba4454949a3927e135d10f712.png