(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…...
GLM-4.7-Flash保姆级教程:CSDN镜像一键启动,30秒开启AI对话
GLM-4.7-Flash保姆级教程:CSDN镜像一键启动,30秒开启AI对话 1. 为什么选择GLM-4.7-Flash? GLM-4.7-Flash是智谱AI推出的新一代开源大语言模型,采用创新的MoE(混合专家)架构,总参数量达30B。相…...
G-Helper技术解析:轻量化华硕笔记本控制架构与实现
G-Helper技术解析:轻量化华硕笔记本控制架构与实现 【免费下载链接】g-helper Lightweight, open-source control tool for ASUS laptops and ROG Ally. Manage performance modes, fans, GPU, battery, and RGB lighting across Zephyrus, Flow, TUF, Strix, Scar,…...
当你的 Agent 会“多轮思考”,Trace 却还停留在单轮:阿里云 CMS OpenClaw 可观测插件升级
作者:王方(方羞) openclaw-cms-plugin 是阿里云云监控 CMS 自研的 OpenClaw 可观测插件,它实现了对 OpenClaw 每次任务调用的链路追踪,符合 GenAI 语义规范,方便用户快速定位和排查问题。具体可参考&#…...
PMP刷题必备口诀-6(题库+答案详细解析)
刷题必背口诀范围说明书四件套,产品描述、可交付、验收标准、除外责核心项内容说明核心考点1. 产品范围描述交付物的核心特征、功能细节明确 “产品是什么”2. 可交付成果最终产出的实物、服务或清单明确 “要交出什么”3. 验收标准可交付物通过验收的硬性条件验收的…...
Qwen3-14B航天领域探索:遥测数据解读、任务规划建议、故障预案生成
Qwen3-14B航天领域探索:遥测数据解读、任务规划建议、故障预案生成 1. 航天领域AI应用概述 航天工程是典型的高复杂度系统工程,涉及海量数据处理、精密任务规划和严苛安全要求。传统工作流程面临三大核心挑战: 遥测数据解读:卫…...
Anko库、AppCompat库
Anko库Anko 是一个由 JetBrains 公司开发的 Kotlin 库,旨在简化 Android 应用程序的开发过程。它通过提供简洁的 API 和基于 Kotlin 的领域特定语言(DSL),减少了样板代码,提升了开发效率和代码可读性。Anko 的最后一个…...
【多模态大模型——跨越感知与认知的鸿沟】7.2 视觉表达SFT(Visual Expression SFT)
目录 第7章 视觉指令微调与数据工程 7.2.1 视觉表达SFT阶段的定义与目标 7.2.1.1 复杂视觉信号到结构化token的映射 7.2.1.2 图像合成、区域检测、视觉推理的统一框架 7.2.1.3 思维链稳定性与过拟合抑制 7.2.2 参数高效微调策略 7.2.2.1 视觉编码器的分层解冻策略 7.2.…...
使用Typora与PP-DocLayoutV3打造个人知识库:从图片笔记到结构化文档
使用Typora与PP-DocLayoutV3打造个人知识库:从图片笔记到结构化文档 你是不是也有过这样的经历?听讲座、看书或者头脑风暴时,习惯性地在纸上写写画画,或者用手机拍下白板上的内容。这些手写笔记和照片,记录了当时的灵…...
OpenClaw+gemma-3-12b-it自动化办公:Excel数据清洗与PPT生成
OpenClawgemma-3-12b-it自动化办公:Excel数据清洗与PPT生成 1. 为什么需要自动化办公助手 上周五下午6点,市场部的同事突然发来一份满是格式问题的销售数据表,要求我在1小时内整理成PPT汇报材料。当我手忙脚乱地复制粘贴时,突然…...
自动送料机构的设计
自动送料机构是现代工业中提升效率的关键部件,其核心作用在于通过机械结构实现物料的精准、连续输送,替代人工操作带来的效率波动与误差风险。无论是金属零件、塑料制品还是粉末状原料,该机构均能根据工艺需求调整输送节奏,确保物…...
