(leetcode算法题)769. 最多能完成排序的块

Q1. 是否能用贪心算法?为什么?
先预设一个策略,每当当前的nums[i]满足可以 "成块",就直接让这个数成块,也就是说之后的遍历过程中不会将这个数在考虑到自己的块内,
"成块" 是指只要只需要将nums[i]放到前面的某个子数组的尾部,然后将这个子数组进行排序,就能得到一个拥有连续自然数的子数组,就称为成块
能够使用谈心算法是因为有如下规律
规律1. 以nums[i]为结尾的成块的子数组,其中的最大值不能小于 i
反证法:假设nums[i]为结尾的成块的子数组,其中最大值小于 i
那么对这个子数组进行排序后,最后一个值即为maxval,且其下标标定位i
子数组最开始的那个下标设为j, 那么子数组中应该有 i - j + 1个元素
又根据成块的定义,这里将会缺少自然数填满i - j + 1个位置矛盾
故,想要成块,子数组的最大值不能小于 i
下面以图示的方法进一步说明,假设红线前的0 1 2已经成块了

如果 nums[7] < 7 那么一定不能成块,因为此时只能有 6 5 4 3 2 1 0 能放入这8个黑框中,
规律2. 以nums[i]为结尾的成块的子数组,其中的最大值不能大于 i
证明与上面类似,矛盾之处在于如果最大值大于 i ,则将会多出来一个元素
所以要想成块只能是maxval == i
class Solution {
public:int maxChunksToSorted(vector<int>& arr) {int n = arr.size();int ret = 0;int curmax = 0;for(int i = 0; i < n; ++i){curmax = max(curmax, arr[i]);if(curmax == i){ret++;}}return ret;}
};
相关文章:
(leetcode算法题)769. 最多能完成排序的块
Q1. 是否能用贪心算法?为什么? 先预设一个策略,每当当前的nums[i]满足可以 "成块",就直接让这个数成块,也就是说之后的遍历过程中不会将这个数在考虑到自己的块内, "成块" 是指只要只…...
高光谱相机的特点
光谱特性 高光谱分辨率:能将光谱范围分割成极窄的波段,光谱分辨率通常达到纳米级甚至亚纳米级,可精确捕捉到不同物质在细微光谱差异上的特征,比如可以区分不同种类的植被因叶绿素含量等差异而在光谱上的细微变化。 多波段探测&a…...
《Spring Framework实战》8:4.1.3.Bean 概述
欢迎观看《Spring Framework实战》视频教程 Spring IoC 容器管理一个或多个 bean。这些 bean 是使用 您提供给容器的配置元数据(例如,以 XML <bean/>定义的形式)。 在容器本身中,这些 bean 定义表示为BeanDefinition对象&a…...
BGP的local_preference本地优先级属性
一、BGP的local preference属性简介 1、local preference公认任意属性 当一条BGP路由器中存在多条去往同一目标网络的BGP路由时,BGP协议会对这些BGP路由属性进行比较,从而筛选出最佳到达目标网络的通达路径。本地优先属性,只在IBGP对等体之间…...
IP地址与端口号
ip地址与端口号 IP地址和端口号是网络通信中的两个重要概念,它们共同构成了网络通信的基础。 IP地址:网络世界的门牌号 定义:IP地址(Internet Protocol Address)是分配给网络设备的数字标签,用于在计算机网…...
Fastapi + vue3 自动化测试平台(2)--日志中间件
FastAPI Vue3 自动化测试平台(2)-- 日志中间件 前言 在开发和运行自动化测试平台时,日志功能是至关重要的一部分。日志不仅能帮助我们快速定位和解决问题,还能作为平台运行的记录依据,为后续分析和优化提供参考。 …...
iOS - AutoreleasePool
1. 基本数据结构 // AutoreleasePool 的基本结构 struct AutoreleasePoolPage {static pthread_key_t const key AUTORELEASE_POOL_KEY;magic_t const magic;id *next; // 指向下一个可存放对象的地址pthread_t const thread; // 所属线程AutoreleasePoolPage …...
1.CSS的复合选择器
1.1 什么是复合选择器 在CSS中,可以根据选择器的类型把选择器分为基础选择器和复合选择器,复合选择器是建立在基础选择器之上,对基础选择器进行组合形成的。 复合选择器可以更精准、更高效的选择目标元素(标签) 复…...
优质内容在个人IP运营中的重要性:以开源AI智能名片商城小程序为应用实例的深度探讨
摘要:在数字化时代,个人品牌(IP)的塑造与传播已成为各行各业提升影响力、吸引用户关注、促进商业转化的关键策略。优质内容作为连接个人IP与目标受众的桥梁,其在个人IP运营中的重要性不言而喻。本文旨在深入探讨优质内…...
Kafka性能测试
kafka是一个大数据消息队列(可以看做为缓存软件) 功能测试:能够读写数据 性能测试:1、测试生产者每秒往kafka写入的最大吞吐量 2、测试消费者每秒从kafka里获取消息最大吞吐量 硬件 3台物理机组成的kafka集群。 内存121G、24…...
解决Docker冲突问题
错误:docker-ce-cli conflicts with 2:docker-1.13.1-210.git7d71120.el7.centos.x86_64 错误:docker-ce conflicts with 2:docker-1.13.1-210.git7d71120.el7.centos.x86_64 您可以尝试添加 --skip-broken 选项来解决该问题 您可以尝试执行:…...
新手入门 React .tsx 项目:从零到实战
🚀 新手入门 React .tsx 项目:从零到实战 💻✨ 如果你是 React 新手,刚接触 .tsx 文件,不要担心!跟着这份指南,一步一步来,你很快就能上手了!👇 Ὅ…...
基于可信数据空间的企业数据要素与流通体系建设(附ppt 下载)
近期,可信数据空间会议召开。大数据系统软件国家工程研究中心总工程师王晨发表了题为《基于可信数据空间的企业数据要素与流通体系建设》主旨演讲。 篇幅限制,部分内容如下:...
二维数组:求最大元素及其所在的行坐标及列坐标(PTA)C语言
求出NM整型数组的最大元素及其所在的行坐标及列坐标(如果最大元素不唯一,选择位置在最前面的一个)。 函数接口定义: int fun(int array[N][M]) ; 注意:函数只需靠return返回最大元素的值, 行、列坐标通过…...
WebRtc01: 课程导学、框架介绍
应用 难点 课程大纲 学习收获 涉及内容 概述 用途 学习收获...
HQChart使用教程30-K线图如何对接第3方数据44-DRAWPIE数据结构
HQChart使用教程30-K线图如何对接第3方数据44-DRAWPIE数据结构 效果图DRAWPIEHQChart代码地址后台数据对接说明示例数据数据结构说明效果图 DRAWPIE DRAWPIE是hqchart插件独有的绘制饼图函数,可以通过麦语法脚本来绘制一个简单的饼图数据。 饼图显示的位置固定在右上角。 下…...
【cuda学习日记】2.2 使用2维网络(grid)和2维块(block)对矩阵进行求和
在2.0中进行了用一维网格和块对一维向量进行了求和。 在2.1中例化了二维的网格和块。 接下来进行2维网络(grid)和2维块(block)对矩阵进行求和。 #include <stdio.h> #include <stdlib.h> #include <time.h> #i…...
深度学习中CUDA环境安装教程
首先说明,本人是小白,一次安装,可能有不对的地方,望包含。 安装CUDA 因为我们是深度学习,很多时候要用到gpu进行训练,所以我们需要一种方式加快训练速度。 通俗地说,CUDA是一种协助“CPU任务分…...
IDEA的常用设置
目录 一、显示顶部工具栏 二、设置编辑区字体按住鼠标滚轮变大变小(看需要设置) 三、设置自动导包和优化导入的包(有的时候还是需要手动导包) 四、设置导入同一个包下的类,超过指定个数的时候,合并为*&a…...
【VUE+ElementUI】通过接口下载blob流文件设置全局Loading加载进度
下载Blob流文件,并以服务形式显示文件下载进度 1、下载接口 增加 config参数,并用...config将该属性加入到请求中; xxapi.js文件中设置downloadFile下载接口 // 下载文件 export function downloadFile(data, config) {return request({ur…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...
RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...
基于TurtleBot3在Gazebo地图实现机器人远程控制
1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...
深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏
一、引言 在深度学习中,我们训练出的神经网络往往非常庞大(比如像 ResNet、YOLOv8、Vision Transformer),虽然精度很高,但“太重”了,运行起来很慢,占用内存大,不适合部署到手机、摄…...
shell脚本质数判断
shell脚本质数判断 shell输入一个正整数,判断是否为质数(素数)shell求1-100内的质数shell求给定数组输出其中的质数 shell输入一个正整数,判断是否为质数(素数) 思路: 1:1 2:1 2 3:1 2 3 4:1 2 3 4 5:1 2 3 4 5-------> 3:2 4:2 3 5:2 3…...
实现p2p的webrtc-srs版本
1. 基本知识 1.1 webrtc 一、WebRTC的本质:实时通信的“网络协议栈”类比 将WebRTC类比为Linux网络协议栈极具洞察力,二者在架构设计和功能定位上高度相似: 分层协议栈架构 Linux网络协议栈:从底层物理层到应用层(如…...
【异常】极端事件的概率衰减方式(指数幂律衰减)
在日常事件中,极端事件的概率衰减方式并非单一模式,而是取决于具体情境和数据生成机制。以下是科学依据和不同衰减形式的分析: 1. 指数衰减(Exponential Decay) 典型场景:当事件服从高斯分布(正态分布)或指数分布时,极端事件的概率呈指数衰减。 数学形式:概率密度函数…...
