LeetCode刷题之路239题滑动窗口最大值

2020年2月21日09:03:09算法 LeetCode评论67阅读模式

题目链接

https://leetcode-cn.com/problems/sliding-window-maximum/文章源自随机的未知-https://sjdwz.com/11126.html

题目内容

给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。文章源自随机的未知-https://sjdwz.com/11126.html

返回滑动窗口中的最大值。文章源自随机的未知-https://sjdwz.com/11126.html

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:文章源自随机的未知-https://sjdwz.com/11126.html

滑动窗口的位置最大值
[1 3 -1] -3 5 3 6 73
1 [3 -1 -3] 5 3 6 73
1 3 [-1 -3 5] 3 6 75
1 3 -1 [-3 5 3] 6 75
1 3 -1 -3 [5 3 6] 76
1 3 -1 -3 5 [3 6 7]7

分析

1、创建一个双端队列用来存储nums数组中元素的索引;
2、创建一个结果数组存储达到窗口大小时,在窗口内的元素;
3、没达到窗口大小时:如果双端队列是空的,那么直接从队尾插入元素的索引,如果双端队列不为空,需要保证双端队列中的索引在nums中的值是递减的。达到窗口大小时,直接将双端队列的头部元素在nums中的值存储到结果数组。文章源自随机的未知-https://sjdwz.com/11126.html

如图:
先放动态图:文章源自随机的未知-https://sjdwz.com/11126.html

LeetCode刷题之路239题滑动窗口最大值
演示图

再放静态图;文章源自随机的未知-https://sjdwz.com/11126.html

LeetCode刷题之路239题滑动窗口最大值
LeetCode刷题之路239题滑动窗口最大值
LeetCode刷题之路239题滑动窗口最大值文章源自随机的未知-https://sjdwz.com/11126.html

LeetCode刷题之路239题滑动窗口最大值
LeetCode刷题之路239题滑动窗口最大值
LeetCode刷题之路239题滑动窗口最大值文章源自随机的未知-https://sjdwz.com/11126.html

LeetCode刷题之路239题滑动窗口最大值
LeetCode刷题之路239题滑动窗口最大值
LeetCode刷题之路239题滑动窗口最大值文章源自随机的未知-https://sjdwz.com/11126.html

LeetCode刷题之路239题滑动窗口最大值
图10
LeetCode刷题之路239题滑动窗口最大值
图11
LeetCode刷题之路239题滑动窗口最大值
图12
LeetCode刷题之路239题滑动窗口最大值
图13
LeetCode刷题之路239题滑动窗口最大值
图14
LeetCode刷题之路239题滑动窗口最大值
图15
LeetCode刷题之路239题滑动窗口最大值
图16
LeetCode刷题之路239题滑动窗口最大值
图17
LeetCode刷题之路239题滑动窗口最大值
图18
LeetCode刷题之路239题滑动窗口最大值
图19
LeetCode刷题之路239题滑动窗口最大值
图20
LeetCode刷题之路239题滑动窗口最大值
图21
LeetCode刷题之路239题滑动窗口最大值
图22
LeetCode刷题之路239题滑动窗口最大值
图23
LeetCode刷题之路239题滑动窗口最大值
图24
LeetCode刷题之路239题滑动窗口最大值
图25
LeetCode刷题之路239题滑动窗口最大值
图26

代码

import jdk.jshell.spi.ExecutionControl;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length<=0)
            throw new RuntimeException("nums是空的!");
        //创建双端队列
        Deque<Integer> deque = new LinkedList<>();
        //创建一个结果的ArrayList
        ArrayList<Integer> resut_array = new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            //如果双端队列不为空,而且到了窗口长度
            if(!deque.isEmpty() && deque.peek() == i-k)
                //移除第一个元素
                deque.pollFirst();
            //保证nums【双端队列中的索引】是一个递减数列
            while(!deque.isEmpty() && nums[deque.getLast()] < nums[i])
                deque.pollLast();

            //把当前元素的索引加到双端队列中
            deque.offer(i);
            //如果是窗口大小
            if(i >= k-1)
                resut_array.add(nums[deque.peek()]);
        }

        //ArrayList转换成整型数组
        int[] res = resut_array.stream().mapToInt(Integer::intValue).toArray();
        return res;
    }
}

欢迎关注

欢迎大家的关注文章源自随机的未知-https://sjdwz.com/11126.html

扫描下方的二维码关注我的微信公众号:随机的未知
LeetCode刷题之路239题滑动窗口最大值文章源自随机的未知-https://sjdwz.com/11126.html

文章源自随机的未知-https://sjdwz.com/11126.html
欢迎关注本站微信公众号:随机的未知 如果喜欢本文,欢迎点赞,收藏,转发,打赏。
  • 本文由 发表于 2020年2月21日09:03:09
  • 转载请注明:来源:随机的未知 本文链接https://sjdwz.com/11126.html
算法

详解堆排序

什么是堆 堆首先是一个完全二叉树,堆分为大顶堆和小顶堆; 大顶堆 : 每个节点的值大于或等于其左右孩子节点的值,称为大顶堆。 小顶堆同理就是每个节点的值小于或等于其左右孩子节点的值。 注意: 每个节点...
算法

详解基数排序

基本思想 基数排序的思想是将整数按位数切割成不同的数字,然后按每个位数分别比较从而得到有序的序列。 例子 本文以数组中元素均为正整数来演示思想。 给定一个数组 arr = < 6, 56, 89 , ...
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定