59Ⅰ.滑动窗口的最大值

参考链接

剑指offer_在线编程_牛客网

剑指 Offer 59 – I. 滑动窗口的最大值-跟着帅地玩转校招，刷爆各类算法题帅地玩Offer

LCR 183. 望远镜中最高的海拔 - 力扣（LeetCode）

个人尝试

很粗糙的一个暴力解法

class Solution {
    public int[] maxAltitude(int[] heights, int limit) {
        if (heights == null || heights.length == 0) return new int[0];
        int j = 0;
        int[] res = new int[heights.length - limit + 1];
        // -10000 <= heights[i] <= 10000
        for (int tmp = 0; tmp < res.length; tmp++) {
            res[tmp] = -10001;
        }
        // 先找出第一个滑动窗口的最大值元素
        while (j < limit) {
            if (heights[j] > res[0]) res[0] = heights[j];
            j++;
        }
        // 滑动窗口每移动一格就要从左边界遍历到右边界寻找最大值
        int i = 1;
        int index = 1;
        for (; j < heights.length; i++, j++, index++) {
            for (int tmp = i; tmp <= j; tmp++) {
                if (res[index] < heights[tmp]) res[index] = heights[tmp];
            }
        }
        return res;
    }
}

优秀题解

class Solution {
    public int[] maxAltitude(int[] heights, int limit) {
        if(heights.length == 0 || limit == 0) return new int[0];
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[heights.length - limit + 1];
        for(int j = 0, i = 1 - limit; j < heights.length; i++, j++) {
            // 队头是否为滑动窗口删除元素
            if(i > 0 && deque.peekFirst() == heights[i - 1])
                deque.removeFirst();
            // 维持非递减队列
            while(!deque.isEmpty() && deque.peekLast() < heights[j])
                deque.removeLast();
            // 滑动窗口新元素进队
            deque.addLast(heights[j]);
            // 队头为滑动窗口最大值
            if(i >= 0)
                res[i] = deque.peekFirst();
        }
        return res;
    }
}

作者：Krahets
链接：https://leetcode.cn/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/solutions/213779/mian-shi-ti-59-i-hua-dong-chuang-kou-de-zui-da-1-6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

个人理解：

维持一个「非递减队列」来保存滑动窗口的「临时最大值队列」，

队列中的队头是滑动窗口中目前元素的最大值，

每当滑动窗口移动时，可能更为 滑动窗口 的最大值 即 队头元素，因此可能需要删除队头元素，

而当新元素进入滑动窗口时，可能成为滑动窗口目前元素的第 1 / 2 / 3... 大的元素，因此需要从队尾开始判断，小于新元素需要出队。