力扣406-根据身高重建队列(java详细题解)

2024-08-31 22:52

本文主要是介绍力扣406-根据身高重建队列(java详细题解),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接:406. 根据身高重建队列 - 力扣(LeetCode)

前情提要:

因为本人最近都来刷贪心类的题目所以该题就默认用贪心方法来做。

贪心方法:局部最优推出全局最优。

如果一个题你觉得可以用局部最优推出全局最优,并且没有反例来反驳的话就可以用贪心来试试。

题目思路:

如果你看过我对于力扣135-分发糖果那篇题解的话,会发现这个题好像跟那个有一点类似。

类似在哪里?

这俩道题都是有俩个维度,这个题分别有k和h俩个维度。

那么遇到这种有俩个维度的题,我们应该优先处理一个维度,再去处理另外一个维度。

那这个题,我们先处理n还是k呢?

如果按照k来从小到大排序,排完之后,会发现k的排列并不符合条件,身高也不符合条件,两个维度哪一个都没确定下来。

所以我们按照n来从大到小排序,那么我们每一个数的前面都是比后面要大的,这样我们就可以确定一个维度,前面节点都比后面节点要高。

然后继续根据每个元素的k来插入到k位置即可。

因为k是前面节点比当前节点大的数量,我们已经按升高排序了,前面节点全比后面高,所以当k等于几,你插入到该位置后面就可以。

举个例子。

在这里插入图片描述

那肯定有人会有疑问 插入到该位置不会对他后面的位置有影响吗 ?

其实不会 ,因为他插入的都是h比他高的人 就算他插进来对比他高的k也不会有任何影响 随便他插到哪里去。

局部最优:优先按身高高的people的k来插入。插入操作过后的people满足队列属性。

全局最优:最后都做完插入操作,整个队列满足题目队列属性。

最终代码:

class Solution {public int[][] reconstructQueue(int[][] people) {//该题与分发糖果有些类似,也是一个多维度的题目//多维度的题目 我们要讲究先把一个维度处理好再处理另一个维度//那么该题到底是先处理k还是处理h呢//如果先处理k 我们按从小到大排 得到的结果不仅k没处理好 h也没处理好 所以我们先处理h//如果先处理h 我们得到了一个根据h从大到小的一个队列 此时每一个数前面都是大与等于自身的//所以此时h就已经处理好了 我们该处理k了//我们从大到小处理k 当他的k等于多少时,就将他插入到该位置//那肯定有人会有疑问 插入到该位置不会对他后面的位置有影响吗 其实不会 //因为他插入的都是h比他高的人 就算他插进来他们的k也不会有任何影响 随便他插到哪里去//局部最优:优先按身高高的people的k来插入。插入操作过后的people满足队列属性//全局最优:最后都做完插入操作,整个队列满足题目队列属性//根据身高降序排 如果身高一样按k升序排 因为k越大 说明他前面大与等于他的越多Arrays.sort(people,(a,b) -> {//h相等时 k按从小到大排if(a[0] == b[0])return a[1] - b[1];//h不相等,按从大到小排return b[0] - a[0];});LinkedList<int []> list = new LinkedList<>();for(int[] arr : people){//将arr插入指定k处list.add(arr[1],arr);}return list.toArray(new int [people.length][]);}
}

这道题代码量很少,但是逻辑可能不是那么好理解,我们可以多画画图,多模拟几遍就能弄懂啦。

这一篇博客就到这了,如果你有什么疑问和想法可以打在评论区,或者私信我。

我很乐意为你解答。那么我们下篇再见!

这篇关于力扣406-根据身高重建队列(java详细题解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1125222

相关文章

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》:本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.

springboot security使用jwt认证方式

《springbootsecurity使用jwt认证方式》:本文主要介绍springbootsecurity使用jwt认证方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录前言代码示例依赖定义mapper定义用户信息的实体beansecurity相关的类提供登录接口测试提供一

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

基于SpringBoot实现文件秒传功能

《基于SpringBoot实现文件秒传功能》在开发Web应用时,文件上传是一个常见需求,然而,当用户需要上传大文件或相同文件多次时,会造成带宽浪费和服务器存储冗余,此时可以使用文件秒传技术通过识别重复... 目录前言文件秒传原理代码实现1. 创建项目基础结构2. 创建上传存储代码3. 创建Result类4.

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath?3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4

Tomcat版本与Java版本的关系及说明

《Tomcat版本与Java版本的关系及说明》:本文主要介绍Tomcat版本与Java版本的关系及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Tomcat版本与Java版本的关系Tomcat历史版本对应的Java版本Tomcat支持哪些版本的pythonJ

springboot security验证码的登录实例

《springbootsecurity验证码的登录实例》:本文主要介绍springbootsecurity验证码的登录实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录前言代码示例引入依赖定义验证码生成器定义获取验证码及认证接口测试获取验证码登录总结前言在spring

SpringBoot日志配置SLF4J和Logback的方法实现

《SpringBoot日志配置SLF4J和Logback的方法实现》日志记录是不可或缺的一部分,本文主要介绍了SpringBoot日志配置SLF4J和Logback的方法实现,文中通过示例代码介绍的非... 目录一、前言二、案例一:初识日志三、案例二:使用Lombok输出日志四、案例三:配置Logback一

springboot security快速使用示例详解

《springbootsecurity快速使用示例详解》:本文主要介绍springbootsecurity快速使用示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录创www.chinasem.cn建spring boot项目生成脚手架配置依赖接口示例代码项目结构启用s