滑动窗口的最大值

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

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

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0)return new int[]{};
        if (nums.length < k) return new int[]{};
        int[] res = new int[nums.length - k + 1];
        int n = nums.length - 1;
        int windowEnd = Math.min(k, n);

        int maxIndex = getMaxIndex(nums, 0, Math.min(k, n));    //计算开始时滑动窗口的最大值的index

        for (int i = 0; i <= n - k + 1; i++) {
            windowEnd = Math.min(i + k - 1, n);                 //计算滑动窗口的右边的index

            if (maxIndex >= i && maxIndex <= windowEnd) {       //判断当前的最大值是否过期
                if (nums[windowEnd] > nums[maxIndex]) {         //如果滑动窗口的最右边的值大于当前的最大值，那么替换最大值的index
                    maxIndex = windowEnd;
                    res[i] = nums[windowEnd];
                } else {                                        //如果滑动窗口的最大值不小于最右边新进来的值，并且当前的最大值没有过期
                    res[i] = nums[maxIndex];
                }
            } else {                                            //如果滑动窗口过期了，重新查找最大值的index
                maxIndex = getMaxIndex(nums, i, windowEnd);
                res[i] = nums[maxIndex];
            }
        }

        return res;
    }

    //获取一个窗口中的最大值的index
    public int getMaxIndex(int[] nums, int start, int end) {
        if (end <= start) return start;
        int max = Integer.MIN_VALUE, index = start;
        for (int i = start; i <= end; i++) {
            if (nums[i] > max) {
                index = i;
                max = nums[i];
            }
        }
        return index;
    }
}

使用双端队列维护窗口中的最大值

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
         if (nums.length == 0) return new int[]{};
        int[] result = new int[nums.length - k + 1];

        Deque<Integer> maxQueue = new LinkedList<>();

        for (int i = 0; i < k; i++) {                                                       //维护最大值队列
            while (!maxQueue.isEmpty() && nums[maxQueue.peekLast()] < nums[i]) {            //如果在一个窗口中，队列前面的某个值小于当前加入队列的值，那么窗口中目前的最大值一定是当前加入队列的值，就可以把前面的值删掉
                maxQueue.pollLast();
            }
            maxQueue.offerLast(i);                                                          //如果当前加入的值小于队列最后的值，那么他就补在最后，等他前面的最大值过期后，他有可能变成窗口中的最大值
        }

        result[0] = nums[maxQueue.peekFirst()];
        for (int i = 1; i < nums.length - k + 1; i++) {
            int windowEnd = i + k - 1;                                                      //计算窗口的最右端位置
            while (!maxQueue.isEmpty() && nums[maxQueue.peekLast()] < nums[windowEnd]) {
                maxQueue.pollLast();
            }
            maxQueue.offerLast(windowEnd);
            if (maxQueue.peekFirst() < i) {                                                 //最大值队列中的元素过期
                maxQueue.pollFirst();                                                       //删除最大值队列中过期的元素
            }
            result[i] = nums[maxQueue.peekFirst()];                                         //当前的最大值
        }

        return result;
    }
}

赏

谢谢你请我吃糖果

微信