todo 剑指 Offer 59 - I. 滑动窗口的最大值



剑指 Offer 59 - I. 滑动窗口的最大值

难度简单 200
给定一个数组 nums 和滑动窗口的大小 k,请找出所有滑动窗口里的最大值。
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
**输出: **[3,3,5,5,6,7] 
**解释: **

滑动窗口的位置                 最大值
—————        —–
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

提示:
你可以假设 *k *总是有效的,在输入数组不为空的情况下,1 ≤ k ≤  输入数组的大小。
注意:本题与主站 239 题相同:https://leetcode-cn.com/problems/sliding-window-maximum/

    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0 || k == 0) return new int[0];
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[nums.length - k + 1];
        for(int j = 0, i = 1 - k; j < nums.length; i++, j++) &#123;
            if(i > 0 && deque.peekFirst() == nums[i - 1])
                deque.removeFirst(); // 删除 deque 中对应的 nums[i-1]
            while(!deque.isEmpty() && deque.peekLast() < nums[j])
                deque.removeLast(); // 保持 deque 递减
            deque.addLast(nums[j]);
            if(i >= 0)
                res[i] = deque.peekFirst();  // 记录窗口最大值
        &#125;
        return res;
    &#125;

https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/solution/mian-shi-ti-59-i-hua-dong-chuang-kou-de-zui-da-1-6/


文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
 上一篇
530. 二叉搜索树的最小绝对差 530. 二叉搜索树的最小绝对差
530. 二叉搜索树的最小绝对差难度简单 233给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值。 示例:输入: 1         3    /   2 输出:1 解释:最小绝对差为 1,其中 2 和 1
下一篇 
203. 移除链表元素 203. 移除链表元素
203. 移除链表元素难度简单 540删除链表中等于给定值 _val _的所有节点。示例:输入: 1->2->6->3->4->5->6, val = 6输出: 1->2->3->4-&
  目录