你知道在给定一个数组和滑动窗口的大小的条件下，如何找出所有滑动窗口里数值的最大值吗?下面给大家分享了三种思路。

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

例：

假如输入数组{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]}

思路1：(简单易懂)

import java.util.*;
public class Solution
{
    public ArrayList < Integer > maxInWindows(int[] num, int size)
    {
        if (num == null || num.length == 0 || size <= 0 || num.length < size)
        {
            return new ArrayList < Integer > ();
        }
        ArrayList < Integer > result = new ArrayList < > ();
        //双端队列，用来记录每个窗口的最大值下标
        LinkedList < Integer > qmax = new LinkedList < > ();
        int index = 0;
        for (int i = 0; i < num.length; i++)
        {
            while (!qmax.isEmpty() && num[qmax.peekLast()] < num[i])
            {
                qmax.pollLast();
            }
            qmax.addLast(i);
            //判断队首元素是否过期
            if (qmax.peekFirst() == i - size)
            {
                qmax.pollFirst();
            }
            //向result列表中加入元素
            if (i >= size - 1)
            {
                result.add(num[qmax.peekFirst()]);
            }
        }
        return result;
    }
}

思路2：

//单调队列，O(n)
class Solution
{
    public:
        vector < int > maxInWindows(const vector < int > & a, unsigned int k)
        {
            vector < int > res;
            deque < int > s;
            for (unsigned int i = 0; i < a.size(); ++i)
            {
                while (s.size() && a[s.back()] <= a[i]) s.pop_back();
                while (s.size() && i - s.front() + 1 > k) s.pop_front();
                s.push_back(i);
                if (k && i + 1 >= k) res.push_back(a[s.front()]);
            }
            return res;
        }
};

思路3：（非常容易理解）

滑动窗口。
1） 判断是否合法输入。
2） 合法， 则找出0~size - 1 中最大值， 其坐标为index。
3） 滑动， 判断index是否过期， 过期则找到窗口中的最大值的index。 添加到list当中。
import java.util.ArrayList;
public class Solution
{
    public ArrayList < Integer > maxInWindows(int[] num, int size)
    {
        ArrayList < Integer > list = new ArrayList < Integer > ();
        if (num == null || num.length < size || size <= 0) return list;
        //int max=num[0];
        int index = 0;
        index = findMax(num, size, 0);
        list.add(num[index]);
        for (int i = size; i < num.length; i++)
        {
            if (index <= i - size)
            {
                index = findMax(num, size, index + 1);
            } //判断是否过期，过期则找到最新的最大值
            if (num[index] < num[i]) index = i;
            list.add(num[index]);
        }
        return list;
    }
    public int findMax(int[] num, int size, int begin)
    {
        //int max=num[begin];
        int index = begin;
        for (int i = begin + 1; i < begin + size; i++)
        {
            if (num[index] < num[i])
            {
                // max=num[i];
                index = i;
            }
        }
        return index;
    }
}

以上的三种思路大家都知道了吧，更多java实例，请继续来本站了解。