剑指Offer-面试题59-I-滑动窗口的最大值

2020-05-07

题目描述

给定一个数组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 ≤输入数组的大小。

思路1

暴力法

代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length == 0){
            return new int[0];
        }
        int i = 0;
        int j =  k - 1;
        int max = 0;
        int[] result = new int[nums.length - k + 1];
        //遍历数组
        while(j < nums.length){
            max = nums[i];
            //遍历窗口，找到最大值
            for(int m=i;m<=j;m++){
                if(max < nums[m]){
                    max = nums[m];
                }
            }
            result[i] = max;
            i++;
            j++;
        }
        return result;
    }
}

思路2

使用单调队列。

算法流程：
- 初始化：双端队列deque，结果列表result，数组长度n；
- 滑动窗口：左边界范围i ∈ [1 - k, n + 1 - k]，右边界范围j ∈ [0, n − 1]
  1. 若窗口元素nums[i]被删除（即i > 0）且队首元素deque[0] == 被删除元素 nums[i - 1]：则队首元素出队；
  2. 删除deque内所有<nums[j]的元素，以保持deque递减；
  3. 将nums[j]添加至deque尾部；
  4. 若已形成窗口（即i>= 0）：将窗口最大值（即队首元素deque[0]）添加至result。
- 返回值：result。
图解

代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length==0 || nums==null || k==0){
            return new int[0];
        }
        Deque<Integer> deque = new LinkedList<>();  //双端队列
        int[] result = new int[nums.length - k + 1];
        //遍历数组
        for(int i=1-k,j=0;j<nums.length;i++,j++){
            //如果左边界i右移时移除的元素是队首元素，则删除队首元素
            if(i>0 && nums[i-1]==deque.peekFirst()){
                deque.pollFirst();
            }
            //将队尾元素<新加进窗口的元素nums[j]的元素移除队列，保持队列单调递减
            while(!deque.isEmpty() && deque.peekLast()<nums[j]){
                deque.pollLast();
            }
            //新加的元素插入队尾
            deque.addLast(nums[j]);
            //若i>=0，证明窗口开始，需要取出队首到result中（队首就是窗口中的最大值）
            if(i >= 0){
                result[i] = deque.peekFirst();
            }

        }
        return result;
    }
}

作者：jyd
链接：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/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。