[100天算法】-最短无序连续子数组(day 70)

题目描述

给定一个整数数组,你需要寻找一个连续的子数组,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。你找到的子数组应是最短的,请输出它的长度。示例 1:输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序,那么整个表都会变为升序排序。
说明 :输入的数组长度范围在 [1, 10,000]。
输入的数组可能包含重复元素 ,所以升序的意思是<=。来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

方法 1:滑动窗口

思路

  • 先找出数组两端已经排好序的两个子数组,剩下的中间那段就是可能的 最短无序连续子数组
  • 但由于这个 无序子数组 中可能会出现需要插入 有序子数组 中的元素,比如图中的数字 4,
  • 我们可以把 无序子数组 看作一个滑动窗口,当出现了上面出现的这种元素时,就扩大窗口的范围;

代码

JavaScript Code

/*** @param {number[]} nums* @return {number}*/
var findUnsortedSubarray = function (nums) {if (nums.length === 0) return 0;let l = 0,r = nums.length - 1;while (nums[l + 1] >= nums[l]) l++;while (nums[r - 1] <= nums[r]) r--;if (r <= l) return 0;const unsorted = nums.slice(l, r + 1),min = Math.min(...unsorted),max = Math.max(...unsorted);while (nums[l - 1] > min) l--;while (nums[r + 1] < max) r++;return r - l + 1;
};

JavaScript Code

/*** @param {number[]} nums* @return {number}*/
var findUnsortedSubarray = function (nums) {if (nums.length === 0) return 0;let l = 0,r = nums.length - 1;while (nums[l + 1] >= nums[l]) l++;while (nums[r - 1] <= nums[r]) r--;if (r <= l) return 0;let p = l,end = r;while (p <= end) {while (nums[p] < nums[l]) l--;while (nums[p] > nums[r]) r++;p++;}return r - (l + 1);
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/187300.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Linux下内网穿透实现云原生观测分析工具的远程访问

&#x1f4d1;前言 本文主要是Linux下内网穿透实现云原生观测分析工具的远程访问设置的文章&#xff0c;如果有什么需要改进的地方还请大佬指出⛺️ &#x1f3ac;作者简介&#xff1a;大家好&#xff0c;我是青衿&#x1f947; ☁️博客首页&#xff1a;CSDN主页放风讲故事 &…

[C/C++]数据结构 链表OJ题:环形链表(如何判断链表是否有环)

题目描述: 给你一个链表的头节点 head &#xff0c;判断链表中是否有环。 如果链表中有某个节点&#xff0c;可以通过连续跟踪 next 指针再次到达&#xff0c;则链表中存在环。 为了表示给定链表中的环&#xff0c;评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置&…

Docker+K8s基础(重要知识点总结)

目录 一、Docker的核心1&#xff0c;Docker引擎2&#xff0c;Docker基础命令3&#xff0c;单个容器运行多个服务进程4&#xff0c;多个容器运行多个服务进程5&#xff0c;备份在容器中运行的数据库6&#xff0c;在宿主机和容器之间共享数据7&#xff0c;在容器之间共享数据8&am…

OSG交互:选中场景模型并高亮显示

1、目的 可以在osg视图中选中指定模型实体,并高亮显示。共分为两种,一种鼠标点选,一种框选。 2、鼠标点选 2.1 功能说明 生成两组对象,一组cow对象可以被选中,另一组robot不能被选中;点击cow对象被选中高亮,点击robot被选中不高亮;点击空白处,弹出“select nothing!…

P6入门:项目初始化2-项目详情之日期Date

前言 使用项目详细信息查看和编辑有关所选项目的详细信息&#xff0c;在项目创建完成后&#xff0c;初始化项目是一项非常重要的工作&#xff0c;涉及需要设置的内容包括项目名&#xff0c;ID,责任人&#xff0c;日历&#xff0c;预算&#xff0c;资金&#xff0c;分类码等等&…

STM32H743XX/STM32H563XX芯片烧录一次后,再次上电无法烧录

近期在使用STM32H563ZIT6这款芯片在开发板上使用正常&#xff0c;烧录到自己打的板子就遇到了芯片烧录一次后&#xff0c;再次上电无法烧录的问题。 遇到问题需要从以下5点进行分析。 首先看下开发板的原理图 1.BOOT0需要拉高。 2.NRST脚在开发板上是悬空的。这里我建议大家…

远程电脑未连接显示器时分辨率太小的问题处理

背景&#xff1a;单位电脑显示器坏了&#xff0c;使用笔记本通过向日葵远程连接&#xff0c;发现分辨率只有800*600并且不能修改&#xff0c;网上找了好久找到了处理方法这里记录一下&#xff0c;主要用到的是一个虚拟显示器软件usbmmidd_v2 1)下载usbmmidd_v2 2&#xff09;…

2022年12月 Python(四级)真题解析#中国电子学会#全国青少年软件编程等级考试

Python等级考试(1~6级)全部真题・点这里 一、单选题(共25题,每题2分,共50分) 第1题 有n个按名称排序的商品,使用对分查找法搜索任何一商品,最多查找次数为5次,则n的值可能为?()(2分) A.5 B.15 C.30 D.35 答案:C 答案解析:对分查找最多查找次数m与个数之间n的…

【星海随笔】SDN neutron (一)

一、SDN的原理&#xff1a; 控制平面与数据平面分离&#xff1a;传统网络中&#xff0c;网络设备同时承担控制和数据转发功能&#xff0c;而SDN将这两个功能分离&#xff0c;使得网络控制集中在一个中心控制器上。 中心控制器&#xff1a;SDN架构中的中心控制器负责网络的全局…

一个“Hello, World”Flask应用程序

如果您访问Flask网站&#xff0c;会看到一个非常简单的示例应用程序&#xff0c;只有5行代码。为了不重复那个简单的示例&#xff0c;我将向您展示一个稍微复杂一些的示例&#xff0c;它将为您编写大型应用程序提供一个良好的基础结构。 应用程序将存在于包中。在Python中&…

aosp定制android系统

目录 AOSP 准备工作(配置) 确定机型和版本 初始化 git安装 curl安装 同步源码 环境变量 创建aosp目录 指定同步版本 解下来安装编译需要的依赖 编译aosp源码 刷入系统 AOSP 全称 Android Open Source Project 是指Android开源项目&#xff0c;它是由Google主导的…

gird 卡片布局

场景一&#xff1a;单元格大小相等 这承载了所有 CSS Grid 中最著名的片段&#xff0c;也是有史以来最伟大的 CSS 技巧之一&#xff1a; 等宽网格响应式卡片实现 .section-content {display: grid;grid-template-columns: repeat(auto-fit, minmax(220px, 1fr));gap: 10px; …

list部分接口模拟实现(c++)

List list简介list基本框架list构造函数list_node结构体的默认构造list类的默认构造 push_back()iteartor迭代器迭代器里面的其他接口const迭代器通过模板参数实现复用operator->() insert()erase()clear()析构函数迭代器区间构造拷贝构造operator() list简介 - list可以在…

使用 pubsub-js 进行消息发布订阅

npm 包地址 github 包地址 pubsub-js 是一个轻量级的 JavaScript 基于主题的消息订阅发布库 &#xff0c;压缩后小于1b。它具有使用简单、性能高效、支持多平台等优点&#xff0c;可以很好地满足各种需求。 功能特点&#xff1a; 无依赖同步解耦ES3 兼容。pubsub-js 能够在…

Angular 由一个bug说起之一:List / Grid的性能问题

在angular中&#xff0c;MatTable构建简单&#xff0c;使用范围广。但某些时候会出现卡顿 卡顿情景&#xff1a; 1&#xff1a;一次性请求太多的数据 2&#xff1a;一次性渲染太多数据&#xff0c;这会花费CPU很多时间 3&#xff1a;行内嵌套复杂的元素 4&#xff1a;使用过多的…

11月份 四川汽车托运报价已经上线

中国人不骗中国人!! 国庆小长假的高峰期过后 放假综合症的你还没痊愈吧 今天给大家整理了9条最新线路 广州到四川的托运单价便宜到&#x1f4a5; 核算下来不过几毛钱&#x1f4b0; 相比起自驾的漫长和疲惫&#x1f697; 托运不得不说真的很省事 - 赠送保险 很多客户第一次运车 …

LeetCode 17. 电话号码的字母组合 中等

题目 - 点击直达 1. 17. 电话号码的字母组合 中等1. 题目详情1. 原题链接2. 题目要求3. 基础框架 2. 解题思路1. 思路分析2. 时间复杂度3. 代码实现 3. 知识与收获 1. 17. 电话号码的字母组合 中等 1. 题目详情 1. 原题链接 LeetCode 17. 电话号码的字母组合 中等 2. 题目要…

unity line renderer绘制的颜色不是想要的红色

线条不是暗红色的&#xff0c;用的是默认的红色 将材质选则为如下即可

C# OpenCvSharp DNN HybridNets 同时处理车辆检测、可驾驶区域分割、车道线分割

效果 项目 代码 using OpenCvSharp; using OpenCvSharp.Dnn; using System; using System.Collections.Generic; using System.Drawing; using System.IO; using System.Linq; using System.Numerics; using System.Text; using System.Windows.Forms;namespace OpenCvSharp_D…

Python使用腾讯云SDK实现对象存储(上传文件、创建桶)

文章目录 1. 开通服务2. 创建存储桶3. 手动上传文件并查看4. python上传文件4.1 找到sdk文档4.2 初始化代码4.3 region获取4.4 secret_id和secret_key获取4.5 上传对象代码4.6 python实现上传文件 5 python创建桶 首先来到腾讯云官网 https://cloud.tencent.com/1. 开通服务 来…