MENU

LeetCode239. 滑动窗口最大值

August 12, 2018 • Read: 314 • LeetCode

题目链接:LeetCode239

题解

暴力可以做,不知道能不能过,这题是一道双端队列求窗口最大值的问题,首先创建一个双端队列,在java中,LinkedList底层实现就是双向链表,用它存储最大值的数组下标。

如果队列不为空并且队列尾部的值nums[qres.peekLast()] <= nums[i],就将尾部的值弹出,直到队列为空或者nums[qres.peekLast()] > nums[i],此时就将这个下标值i进队

当窗口的左边界的下标i-k==qres.peekFirst(),就弹出头元素,因为此时该元素已经不在窗口内,过期了。剩下的情况就是当窗口长度完全为3之后,每次移动都获取队头元素即可

代码
class Solution {
    static LinkedList<Integer> qres = new LinkedList<Integer>();
    public static int[] maxSlidingWindow(int[] arr,int k) {
        qres.clear();
        if(arr == null || arr.length == 0)
            return new int[] {};
        int index = 0;
        int[] res = new int[arr.length - k + 1];
        for(int i = 0;i < arr.length;i++) {
            while(!qres.isEmpty() && arr[qres.peekLast()] <= arr[i])
                qres.removeLast();
            qres.addLast(i);
            if(qres.peekFirst() == i - k)
                qres.removeFirst();
            if(i >= k - 1)
                res[index++] = arr[qres.peekFirst()];
        }
        return res;
    }
}
最后编辑于: October 7, 2018
Archives Tip
QR Code for this page
Tipping QR Code