当前位置：首页 > 编程日记 > 正文

LeetCode实战：滑动窗口最大值

编程日记 2024-09-28 17:00:00

题目英文

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7] 
Explanation: Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       31 [3  -1  -3] 5  3  6  7       31  3 [-1  -3  5] 3  6  7       51  3  -1 [-3  5  3] 6  7       51  3  -1  -3 [5  3  6] 7       61  3  -1  -3  5 [3  6  7]      7

Note:

You may assume k is always valid, 1 ≤ k ≤ input array’s size for non-empty array.

Follow up:

Could you solve it in linear time?

题目中文

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 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       31 [3  -1  -3] 5  3  6  7       31  3 [-1  -3  5] 3  6  7       51  3  -1 [-3  5  3] 6  7       51  3  -1  -3 [5  3  6] 7       61  3  -1  -3  5 [3  6  7]      7

提示：

你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。

进阶：

你能在线性时间复杂度内解决此题吗？

算法实现

实现一：暴力寻找每个窗口的最大值。

public class Solution {public int[] MaxSlidingWindow(int[] nums, int k) {int len = nums.Length;if (len == 0)return nums;int[] result = new int[len - k + 1];for (int i = 0; i < result.Length; i++){result[i] = GetMax(nums, i, i + k);}return result;        }public int GetMax(int[] arr,int start,int end){int max = int.MinValue;for (int i = start; i < end; i++){if (arr[i] > max)max = arr[i];}return max;}    
}

实现二：如果想提升时间效率就需要使用结构了。

双向队列的结构

public class MyCircularDeque
{private int _pFront;private int _pRear;private readonly int[] _dataset;private int _length;private int _maxSize;/** Initialize your data structure here. Set the size of the deque to be k. */public MyCircularDeque(int k){_dataset = new int[k];_length = 0;_maxSize = k;_pFront = 0;_pRear = 0;}/** Adds an item at the front of Deque. Return true if the operation is successful. */public bool InsertFront(int value){if (_length == _maxSize)return false;_pFront = (_pFront - 1 + _maxSize) % _maxSize;_dataset[_pFront] = value;_length++;return true;}/** Adds an item at the rear of Deque. Return true if the operation is successful. */public bool InsertLast(int value){if (_length == _maxSize)return false;_dataset[_pRear] = value;_pRear = (_pRear + 1) % _maxSize;_length++;return true;}/** Deletes an item from the front of Deque. Return true if the operation is successful. */public bool DeleteFront(){if (_length == 0)return false;_pFront = (_pFront + 1) % _maxSize;_length--;return true;}/** Deletes an item from the rear of Deque. Return true if the operation is successful. */public bool DeleteLast(){if (_length == 0)return false;_pRear = (_pRear - 1 + _maxSize) % _maxSize;_length--;return true;}/** Get the front item from the deque. */public int GetFront(){if (_length == 0)return -1;return _dataset[_pFront];}/** Get the last item from the deque. */public int GetRear(){if (_length == 0)return -1;int index = (_pRear - 1 + _maxSize) % _maxSize;return _dataset[index];}/** Checks whether the circular deque is empty or not. */public bool IsEmpty(){return _length == 0;}/** Checks whether the circular deque is full or not. */public bool IsFull(){return _length == _maxSize;}
}

代码实现

public class Solution {public int[] MaxSlidingWindow(int[] nums, int k) {int len = nums.Length;if (len == 0)return nums;int[] result = new int[len - k + 1];//保存当前窗口最大值的数组位置 保证队列中数组位置的数值按从大到小排序MyCircularDeque deque = new MyCircularDeque(len);for (int i = 0; i < len; i++){// 保证从大到小 如果前面数小则需要依次弹出，直至满足要求while (deque.IsEmpty() == false && nums[deque.GetRear()] <= nums[i]){deque.DeleteLast();}//添加当前值对应的数组下标deque.InsertLast(i);// 判断当前队列中队首的值是否有效if (deque.GetFront() <= i - k){deque.DeleteFront();}// 当窗口长度为k时 保存当前窗口中最大值if (i + 1 >= k){result[i + 1 - k] = nums[deque.GetFront()];}}return result;        }
}

实验结果

实现一：

状态：通过
18 / 18 个通过测试用例
执行用时: 472 ms, 在所有 C# 提交中击败了 53.33% 的用户
内存消耗: 34.3 MB, 在所有 C# 提交中击败了 50.00% 的用户

提交记录

实现二：

状态：通过
18 / 18 个通过测试用例
执行用时: 412 ms, 在所有 C# 提交中击败了 82.76% 的用户
内存消耗: 34.9 MB, 在所有 C# 提交中击败了 10.00% 的用户

提交记录

相关图文：

LeetCode实战：两数之和
LeetCode实战：三数之和
LeetCode实战：缺失的第一个正数
LeetCode实战：求众数
LeetCode实战：快乐数
LeetCode实战：删除链表的倒数第N个节点
LeetCode实战：合并两个有序链表
LeetCode实战：合并K个排序链表
LeetCode实战：两两交换链表中的节点
LeetCode实战：旋转链表
LeetCode实战：环形链表
LeetCode实战：有效的括号
LeetCode实战：最长有效括号
LeetCode实战：逆波兰表达式求值
LeetCode实战：相同的树
LeetCode实战：对称二叉树
LeetCode实战：二叉树的最大深度
LeetCode实战：将有序数组转换为二叉搜索树
LeetCode实战：搜索二维矩阵

https://www.dkcj.cn/info/20727.html

Partial Class部分类

Partial Class ，部分类或者分布类。顾名思义，就是将一个类分成多个部分。比如说：一个类中有3个方法，在VS 2005将该类中3个方法分别存放在3个不同的.cs文件中。这样做的好处：1、一个大型的项目类可以同时分成不同的区块…

编程日记2024/09/28 16:50:00

表格中td限宽溢出以省略号代替

table.ms-listviewtable {table-layout:fixed;width: 100%; } table.ms-listviewtable td[role"gridcell"]{white-space:nowrap;text-overflow:ellipsis;-moz-text-overflow: ellipsis;overflow:hidden; } 转载于:https://www.cnblogs.com/JaneBlog/p/7490445.html

编程日记2024/09/28 16:40:00

【UI设计培训基础知识】设计中的点线面-线

UI设计所要学习的知识有很多，想要在后期的工作中稳稳当当，基础知识一定要扎实，下面就是小编为大家整理的一份关于UI设计培训基础知识的相关内容，主要讲的是设计中的点线面-线，来看看下面的详细资料吧。点的移动形成一…

编程日记2024/09/28 16:30:00

场面话大全，绝对受用一生

◆ 父母生日祝酒辞尊敬的各位领导、各们长辈、各们亲朋好友：大家好！ 在这喜庆的日子里，我们高兴地迎来了敬爱的父亲（母亲）XX岁的生日。今天，我们欢聚一堂，举行父亲（母亲&#xff09…

编程日记2024/09/28 16:20:00

LeetCode实战：爬楼梯

题目英文 You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Note: Given n will be a positive integer. Example 1: Input: 2 Output: 2 Exp…

编程日记2024/09/28 16:10:00

Visual Studio Remote Debugger(for 2005/2008) .net远程调试转

我采用虚机的方式模拟了局域网环境，以下是我操作的步骤（client代表客户端，server代表调试机）： 建立ASP.NET项目(client)：简单写了点Code 代码 1 protectedvoidPage_Load(objectsender, EventArgs e)2 {3 in…

编程日记2024/09/28 16:00:00

UI设计师必备技能，看看你都学会了吗?

想要成为一名合格的UI设计师，是要有这几项必备技能的，学会这些必备技能，那么后期的工作会进行的相当顺利，下面小编就为大家详细的介绍一下UI设计师必备技能都有哪些? UI设计师必备技能，看看你都学会了吗? 1、设计软件…

编程日记2024/09/28 15:50:00

CSS中关于清除浮动的问题

1.采用:after的方法清除浮动优点：避免在html里插入多余的标签详情：http://www.positioniseverything.net/easyclearing.html 整理成一个通用的.clearfix .clearfix:after {content:".";display:block;height:0;clear:both;visibility:hidden…

编程日记2024/09/28 15:40:00

LeetCode实战：x 的平方根

题目英文 Implement int sqrt(int x). Compute and return the square root of x, where x is guaranteed to be a non-negative integer. Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned. …

编程日记2024/09/28 15:30:00

Vue中组件数据的传递

Vue中组件的作用域是隔离的，父组件中的数值子组件看不到！也就是说，用angular作比喻，组件的scope天生是scope:()的！如果父组件需要往子组件中传数据，此时应该使用标签属性： <div id"app&…

编程日记2024/09/28 15:20:00

学习Python往哪个方向发展好

Python近几年在IT行业的发展前景是非常可观的，尤其是在人工智能领域这一块，吸引了很多人的关注，但不仅仅是人工智能领域，Python在很多其他地方也是非常有发展前景的，那么具体学习Python往那个方向发展好呢?来看看下面…

编程日记2024/09/28 15:10:00

开发人员绩效考核中有效bug数的统计

我们都知道,开发人员的考核中,bug这块占了一定的比重,那么我们在统计每个开发人员的bug数时,显然要做到有效,不能把缺陷管理系统上的bug不经过处理,就直接进行统计. 如何统计有效bug数呢? 我们从bug的属性上进行控制,分析如下: bug问题来源: 需求问题架构问题设计问题编码问题…

编程日记2024/09/28 15:00:00

LeetCode实战：反转字符串

题目英文 Write a function that reverses a string. The input string is given as an array of characters char[]. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. You may assume al…

编程日记2024/09/28 14:50:00

HTML5 监听当前位置

2019独角兽企业重金招聘Python工程师标准>>> <!DOCTYPE html> <html><head><meta charset"UTF-8"><title>监听当前位置</title><meta name"viewport" content"widthdevice-width, initial-scale1,…

编程日记2024/09/28 14:40:00

Python培训教程之Python基础知识点梳理

Python语言是入门IT行业比较快速且简单的一门编程语言，学习Python语言不仅有着非常大的发展空间，还可以有一个非常好的工作，下面小编就来给大家分享一篇Python培训教程之Python基础知识点梳理。 Python培训教程之Python基础知识点梳理&#x…

编程日记2024/09/28 14:30:00

技术图文：如何通过挂单刷 BigOne 的贡献值？

背景这段时间 BigOne 开启了「挂单捡钱七天乐」活动，凡在活动期间进行有效挂单的用户均可获得「贡献值」奖励。详细情况如下： 1. 参与交易对 BTC/USDT, EOS/USDT, ETH/USDT, ONE/USDT, EOS/BTC, ETH/BTC, EOS/ETH，共 7 个交易对。 2. …

编程日记2024/09/28 14:20:00

ASP.NET - Page 的生命周期

初始化(Initialization) 页面被请求时，第一个被执行的总是构造函数(constructor). 你可以在这里初始化很多自定义属性或对象。不过这里有一些限制，因为 page 还没有被完全初始化。特别地，你必须使用 HttpContext.Current 来访问 QueryString,…

编程日记2024/09/28 14:10:00

【视频点播最佳实践】视频点播播放异常排查

阿里云视频点播是集音视频采集、编辑、上传、自动化转码处理、媒体资源管理、分发加速、视频播放于一体的一站式音视频点播解决方案。但是对于使用者来说经常遇到的问题即是视频点播中的视频如何对外提供服务，并且当播放出现异常时如何进行排查呢？本文主…

编程日记2024/09/28 14:00:00

Java程序员技术培训需要培训哪些?

随着java技术行业的不断发展，越来越多的人想要学习java技术，那么想要成为一名优秀的java工程师，需要学习的技术知识是非常多的，下面小编就为大家详细的介绍一下Java程序员技术培训需要培训哪些? Java程序员技术培训需要培训哪些?…

编程日记2024/09/28 13:50:00

VS2008 VS2010发布网站时如何产生固定命名的 Dll 文件

VS2008 发布网站时如何产生固定命名的 Dll 文件dev.firnow.com 时间 ： 2010-12-08 作者：网络编辑：fnw 点击： 82 [ 评论 ]--VS2008 在发布网站时，bin 目录里为所有 cs 生成的 dll 文件每次都是随机命名的&#…

编程日记2024/09/28 13:40:00

LeetCode实战：两数相加

题目英文 You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. You may assume the two nu…

编程日记2024/09/28 13:30:00