本文为稀土掘金技术社区首发签约文章，14天内禁止转载，14天后未获授权禁止转载，侵权必究！

大家好，又见面了。

在服务端开发中，缓存常常被当做系统性能扛压的不二之选。在实施方案上，缓存使用策略虽有一定普适性，却也并非完全绝对，需要结合实际的项目诉求与场景进行综合权衡与考量，进而得出符合自己项目的最佳实践。

缓存使用的演进

现有这么一个系统：

一个互动论坛系统，用户登录系统之后，可以在论坛上查看帖子列表、查看帖子详情、发表帖子、评论帖子、为帖子点赞等操作。

系统中所有的配置数据与业务数据均存储在数据库中。随着业务的发展，注册用户量越来越多，然后整个系统的响应速度也越来越慢，用户体验越来越差，用户逐渐出现流失。

本地缓存的牛刀小试

为了挽救这一局面，开发人员需要介入去分析性能瓶颈并尝试优化提升响应速度，并很快找到响应慢的瓶颈在数据库的频繁操作，于是想到了使用缓存来解决问题。

于是，开发人员在项目中使用了基于接口维度的短期缓存，对每个接口的请求参数（帖子ID）与响应内容缓存一定的时间（比如1分钟），对于相同的请求，如果匹配到缓存则直接返回缓存的结果即可，不用再次去执行查询数据库以及业务维度的运算逻辑。

JAVA中有很多的开源框架都有提供类似的能力支持，比如Ehcache或者Guava Cache、Caffeine Cache等，可以通过简单的添加注解的方式就实现上述需要的缓存效果。比如使用Ehcache来实现接口接口缓存的时候，代码使用方式如下（这里先简单的演示下，后续的系列文档中会专门对这些框架进行深入的探讨）：

1
2
3
4
5

java复制代码@Cacheable(value="UserDetailCache", key="#userId")
public UserDetail queryUserDetailById(String userId) {
    UserEntity userEntity = userMapper.queryByUserId(userId);
    return convertEntityToUserDetail(userEntity);
}

基上面的本地缓存策略改动后重新上线，整体的响应性能上果然提升了很多。本地缓存的策略虽然有效地提升了处理请求的速度，但新的问题也随之浮现。有用户反馈，社区内的帖子列表多次刷新后会出现内容不一致的情况，有的帖子刷新之后会从列表消失，多次刷新后偶尔会出现。

其实这就是本地缓存在集群多节点场景下会遇到的一个很常见的缓存漂移现象：

因为业务集群存在多个节点，而缓存是每个业务节点本地独立构建的，所以才出现了更新场景导致的本地缓存不一致的问题，进而表现为上述问题现象。

集中式缓存的初露锋芒

为了解决集群内多个节点间执行写操作之后，各节点本地缓存不一致的问题，开发人员想到可以构建一个集中式缓存，然后所有业务节点都读取或者更新同一份缓存数据，这样就可以完美地解决节点间缓存不一致的问题了。

业界成熟的集中式缓存有很多，最出名的莫过于很多人都耳熟能详的Redis，或者是在各种面试中常常被拿来与Redis进行比较的Memcached。也正是由于它们出色的自身性能表现，在当前的各种分布式系统中，Redis近乎已经成为了一种标配，常常与MySQL等持久化数据库搭配使用，放在数据库前面进行扛压。比如下面图中示例的一种最简化版本的组网架构：

开发人员对缓存进行了整改，将本地缓存改为了Redis集中式缓存。这样一来：

1. 缓存不一致问题解决：解决了各个节点间数据不一致的问题。
2. 单机内存容量限制解决：使用了Redis这种分布式的集中式缓存，扩大了内存缓存的容量范围，可以顺便将很多业务层面的数据全部加载到Redis中分片进行缓存，性能也相比而言得到了提升。

似乎使用集中式缓存已经是分布式系统中的最优解了，但是现实情况真的就这么简单么？也不尽然！

多级缓存的珠联璧合

在尝到了集中式缓存的甜头之后，暖心的程序员们想到要彻底为数据库减压，将所有业务中需要频繁使用的数据全部同步存储到Redis中，然后业务使用的时候直接从Redis中获取相关数据，大大地减少了数据库的请求频次。但是改完上线之后，发现有些处理流程中并没有太大的性能提升。缘何如此？只因为对集中式缓存的过分滥用！分析发现这些流程的处理需要涉及大量的交互与数据整合逻辑，一个流程需要访问近乎30次Redis！虽然Redis的单次请求处理性能极高，甚至可以达到微秒级别的响应速度，但是每个流程里面几十次的网络IO交互，导致频繁的IO请求，以及线程的阻塞与唤醒切换交替，使得系统在线程上下文切换层面浪费巨大。

那么，要想破局，最常规的手段便是尝试降低对集中式缓存（如Redis）的请求数量，降低网络IO交互次数。而如何来降低呢？ —— 又回到了本地缓存！集中式缓存并非是分布式系统中提升性能的银弹，但我们可以将本地缓存与集中式缓存结合起来使用，取长补短，实现效果最大化。如图所示：

上图演示的也即多级缓存的策略。具体而言：

• 对于一些变更频率比较高的数据，采用集中式缓存，这样可以确保数据变更之后所有节点都可以实时感知到，确保数据一致；
• 对于一些极少变更的数据（比如一些系统配置项）或者是一些对短期一致性要求不高的数据（比如用户昵称、签名等）则采用本地缓存，大大减少对远端集中式缓存的网络IO次数。

这样一来，系统的响应性能又得到了进一步的提升。

通过对缓存使用策略的一步步演进，我们可以感受到缓存的恰当使用对系统性能的帮助作用。

无处不在的缓存

缓存存在的初衷，就是为了兼容两个处理速度不一致的场景对接适配的。在我们的日常生活中，也常常可以看到“缓存”的影子。比如对于几年前比较盛行的那种带桶的净水器（见下图），由于净水的功率比较小，导致实时过滤得到纯净水的水流特别的缓慢，用户倒一杯水要等2分钟，体验太差，所以配了个蓄水桶，净水机先慢慢的将净化后的水存储到桶中，然后用户倒水的时候可以从桶里快速的倒出，无需焦急等待 —— 这个蓄水桶，便是一个缓存器。

编码源于生活，CPU的高速缓存设计就是这一生活实践在计算机领域的原样复制。缓存可以说在软件世界里无处不在，除了我们自己的业务系统外，在网络传输、操作系统、中间件、基础框架中都可以看到缓存的影子。如：

1. 网络传输场景。

比如ARP协议，基于ARP缓存表进行IP与终端硬件MAC地址之间的缓存映射。这样与对端主机之间有通信需求的时候，就可以在ARP缓存中查找到IP对应的对端设备MAC地址，避免每次请求都需要去发送ARP请求查询MAC地址。

2. MyBatis的多级缓存。

MyBatis作为JAVA体系中被广泛使用的数据库操作框架，其内部为了提升处理效率，构建了一级缓存与二级缓存，大大减少了对SQL的重复执行次数。

3. CPU中的缓存。

CPU与内存之间有个临时存储器（高速缓存），容量虽比内存小，但是处理速度却远快于普通内存。高速缓存的机制，有效地解决了CPU运算速度与内存读写速度不匹配的问题。

缓存的使用场景

缓存作为互联网类软件系统架构与实现中的基石般的存在，不仅仅是在系统扛压或者接口处理速度提升等性能优化方案，在其他多个方面都可以发挥其独一无二的关键价值。下面就让我们一起来看看缓存都可以用在哪些场景上，可以解决我们哪方面的痛点。

降低自身CPU消耗

如前面章节中提到的项目实例，缓存最典型的使用场景就是用在系统的性能优化上。而在性能优化层面，一个经典的策略就是“空间换时间”。比如：

• 在数据库表中做一些字段冗备。

比如用户表T_User和部门表T_Department，在T_User表中除了有个Department_Id字段与T_Department表进行关联之外，还额外在T_User表中存储Department_Name值。这样在很多需要展示用户所属部门信息的时候就省去了多表关联查询的操作。

• 对一些中间处理结果进行存储。

比如系统中的数据报表模块，需要对整个系统内所有的关联业务数据进行计算统计，且需要多张表多来源数据之间的综合汇总之后才能得到最终的结果，整个过程的计算非常的耗时。如果借助缓存，则可以将一些中间计算结果进行暂存，然后报表请求中基于中间结果进行二次简单处理即可。这样可以大大降低基于请求触发的实时计算量。

在“空间换时间”实施策略中，缓存是该策略的核心、也是被使用的最为广泛的一种方案。借助缓存，可以将一些CPU耗时计算的处理结果进行缓存复用，以降低重复计算工作量，达到降低CPU占用的效果。

减少对外IO交互

上面介绍的使用缓存是为了不断降低请求处理时对自身CPU占用，进而提升服务的处理性能。这里我们介绍缓存的另一典型使用场景，就是减少系统对外依赖的请求频次。即通过将一些从远端请求回来的响应结果进行缓存，后面直接使用此缓存结果而无需再次发起网络IO请求交互。

对于服务端而言，通过构建缓存的方式来减少自身对外的IO请求，主要有几个考量出发点：

1. 从自身性能层面考虑，减少对外IO操作，降低了对外接口的响应时延，也对服务端自身处理性能有一定提升。
2. 从对端服务稳定性层面考虑，避免对端服务负载过大。很多时候调用方和被调用方系统的承压能力是不匹配的，甚至有些被调用方系统可能是不承压的。为了避免将对端服务压垮，需要调用方缓存请求结果，降低IO请求。
3. 从自身可靠性层面而言，将一些远端服务请求到的结果缓存起来，即使远端服务出现故障，自身业务依旧可以基于缓存数据进行正常业务处理，起到一个兜底作用，提升自身的抗风险能力。

在分布式系统服务治理范畴内，服务注册管理服务是必不可少的，比如SpringCloud家族的Eureka，或者是Alibaba开源的Nacos。它们对于缓存的利用，可以说是对上面所提几点的完美阐述。

以Nacos为例：

除了上述的因素之外，对一些移动端APP或者H5界面而言，缓存的使用还有一个层面的考虑，即降低用户的流量消耗，通过将一些资源类数据缓存到本地，避免反复去下载，给用户省点流量，也可以提升用户的使用体验（界面渲染速度快，减少出现白屏等待的情况）。

提升用户个性化体验

缓存除了在系统性能提升或系统可靠性兜底等场景发挥价值外，在APP或者web类用户侧产品中，还经常被用于存储一些临时非永久的个性化使用习惯配置或者身份数据，以提升用户的个性化使用体验。

• 缓存cookie、session等身份鉴权信息，这样就可以避免用户每次访问都需要进行身份验证。

• 记住一些用户上次操作习惯，比如用户在一个页面上将列表分页查询设置为100条/页，则后续在系统内访问其它列表页面时，都沿用这一设置。
• 缓存用户的一些本地设置，这个主要是APP端常用的功能，可以在缓存中保存些与当前设备绑定的设置信息，仅对当前设备有效。比如同一个账号登录某个APP，用户希望在手机端可以显示深色主题，而PAD端则显示浅色主体，这种基于设备的个性化设置，可以缓存到设备本身即可。

业务与缓存的集成模式

如前所述，我们可以在不同的方面使用缓存来辅助达成项目在某些方面的诉求。而根据使用场景的不同，在结合缓存进行业务逻辑实现的时候，也会存在不同的架构模式，典型的会有旁路型缓存、穿透型缓存与异步型缓存三种。

旁路型缓存

在旁路型缓存模式中，业务自行负责与缓存以及数据库之间的交互，可以自由决定缓存未命中场景的处理策略，更加契合大部分业务场景的定制化诉求。

由于业务模块自行实现缓存与数据库之间的数据写入与更新的逻辑，实际实现的时候需要注意下在高并发场景的数据一致性问题，以及可能会出现的缓存击穿、缓存穿透、缓存雪崩等问题的防护。

旁路型缓存是实际业务中最常使用的一种架构模式，在后面的内容中，我们还会不断的涉及到旁路缓存中相关的内容。

穿透型缓存

穿透型缓存在实际业务中使用的较少，主要是应用在一些缓存类的中间件中，或者在一些大型系统中专门的数据管理模块中使用。

一般情况下，业务使用缓存的时候，会是先尝试读取缓存，在尝试读取DB，而使用穿透型缓存架构时，会有专门模块将这些动作封装成黑盒的，业务模块不会与数据库进行直接交互。如下图所示：

这种模式对业务而言是比较友好的，业务只需调用缓存接口即可，无需自行实现缓存与DB之间的交互策略。

异步型缓存

还有一种缓存的使用模式，可以看作是穿透型缓存的演进异化版本，其使用场景也相对较少，即异步型缓存。其主要策略就是业务侧请求的实时读写交互都是基于缓存进行，任何数据的读写也完全基于缓存进行操作。此外，单独实现一个数据持久化操作(独立线程或者进程中执行)，用于将缓存中变更的数据写入到数据库中。

这种情况，实时业务读写请求完全基于缓存进行，而将数据库仅仅作为一个数据持久化存储的备份盘。由于实时业务请求仅与缓存进行交互，所以在性能上可以得到更好的表现。但是这种模式也存在一个致命的问题：数据可靠性！因为是异步操作，所以在下一次数据写入DB前，会有一段时间数据仅存在于缓存中，一旦缓存服务宕机，这部分数据将会丢失。所以这种模式仅适用于对数据一致性要求不是特别高的场景。

缓存的优秀实践

缓存与持久化存储的一个很大的不同点就是缓存的定位应该是一种辅助角色，是一种锦上添花般的存在。

缓存也是一把双刃剑，基于缓存可以大幅提升我们的系统并发与承压能力，但稍不留神也可能会让我们的系统陷入灭顶之灾。所以我们在决定使用缓存的时候，需要知晓缓存设计与使用的一些关键要点，才可以让我们在使用的时候更加游刃有余。

可删除重建

可删除重建，这是缓存与持久化存储最大的一个差别。缓存的定位一定是为了辅助业务处理而生的，也就是说缓存有则使用，没有也不会影响到我们具体的业务运转。此外，即使我们的缓存数据除了问题，我们也可以将其删除重建。

这一点在APP类的产品中体现的会比较明显。比如对于微信APP的缓存，就有明确的提示说缓存可以删除而不会影响其功能使用：

同样地，我们也可以去放心的清理浏览器的缓存，而不用担心清理之后我们浏览器或者网页的功能会出现异常（最多就是需要重新下载或者重建缓存数据，速度会有一些慢）。

相同的逻辑，在服务端构建的一些缓存，也应该具备此特性。比如基于内存的缓存，当业务进程重启后，应该有途径可以将缓存重建出来（比如从MySQL中加载数据然后构建缓存，或者是缓存从0开始基于请求触发而构建）。

有兜底屏障

缓存作为高并发类系统中的核心组件，负责抗住大部分的并发请求，一旦缓存组件出问题，往往对整个系统会造成毁灭性的打击。所以我们的缓存在实现的时候必须要有充足且完备的兜底与自恢复机制。需要做到以下几点：

• 关注下缓存数据量超出承受范围的处理策略，比如定好数据的淘汰机制。
• 避免缓存集中失效，比如批量加载数据到缓存的时候随机打散过期时间，避免同一时间大批量缓存失效引发缓存雪崩问题。
• 有效地冷数据预热加载机制，以及热点数据防过期机制，避免出现大量对冷数据的请求无法命中缓存或者热点数据突然失效，导致缓存击穿问题。
• 合理的防身自保手段，比如采用布隆过滤器机制，避免被恶意请求攻陷，导致缓存穿透类的问题。

缓存的可靠性与兜底策略设计，是一个宏大且宽泛的命题，在本系列专栏后续的文章中，我们会逐个深入的探讨。

关注缓存的一致性保证

在高并发类的系统中进行数据更新的时候，缓存与数据库的数据一致性问题，是一个永远无法绕过的话题。对于基于旁路型缓存的大部分业务而言，数据更新操作，一般可以组合出几种不同的处理策略：

• 先更新缓存，再更新数据库
• 先更新数据库， 再更新缓存
• 先删除缓存，再更新数据库
• 先更新数据库，再删除缓存

由于大部分数据库都支持事务，而几乎所有的缓存操作都不具有事务性。所以在一些写操作并发不是特别高且一致性要求不是特别强烈的情况下，可以简单的借助数据库的事务进行控制。比如先更新数据库再更新缓存，如果缓存更新失败则回滚数据库事务。

然而在一些并发请求特别高的时候，基于事务控制来保证数据一致性往往会对性能造成影响，且事务隔离级别设置的越高影响越大，所以也可以采用一些其它辅助策略，来替代事务的控制，如重试机制、或异步补偿机制、或多者结合方式等。

比如下图所示的这种策略：

上图的数据更新处理策略，可以有效地保证数据的最终一致性，降低极端情况可能出现数据不一致的概率，并兜底增加了数据不一致时的自恢复能力。

数据一致性保证作为缓存的另一个重要命题，我们会在本系列专栏后续的文章中专门进行深入的剖析。

总结回顾

本篇文章的内容中，我们对缓存的各个方面进行了一个简单的阐述与了解，也可以看出缓存对于一个软件系统的重要价值。通过对缓存的合理、充分利用，可以大大的增强我们的系统承压性能、提升产品的用户体验。

缓存作为高并发系统中的神兵利器被广泛使用，堪称高并发系统的基石之一。而缓存的内容还远远不止我们本篇文档中所介绍的这些、它是一个非常宏大的命题。

为了能够将缓存的方方面面彻底的讲透、讲全，在接下来的一段时间里，我会以系列专栏的形式，从不同的角度对缓存的方方面面进行探讨。不仅仅着眼于如何去使用缓存、也一起聊聊缓存设计中的一些哲学理念 —— 这一点是我觉得更有价值的一点，因为这些理念对提升我们的软件架构认知、完善我们的软件设计思维有很大的指导与借鉴意义。

所以，如果你有兴趣，欢迎关注本系列专栏（深入理解缓存原理与实战设计），我会以我一贯的行文风格，用最简单的语言讲透复杂的逻辑，期待一起切磋、共同成长。

我是悟道，聊技术、又不仅仅聊技术~

如果觉得有用，请点赞 + 关注让我感受到您的支持。也可以关注下我的公众号【架构悟道】，获取更及时的更新。

期待与你一起探讨，一起成长为更好的自己。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。

计算机系统是程序员的知识体系中最基础的理论知识，你越早掌握这些知识，你就能越早享受知识带来的 “复利效应”。

本文是计算机系统系列的第 2 篇文章，完整文章目录请移步到文章末尾~

前言

大家好，我是小彭。

上一篇文章里，我们讨论了可计算问题与图灵机的计算机模型。在理解了图灵机模型后，我们将从和图灵同时代的另一位计算机科学家提出的 “冯·诺依曼架构” 开始，正式开始计算机组成原理的核心内容。

那么，冯·诺依曼架构是怎样的结构呢，冯·诺依曼架构是基于图灵机的吗，我们现在用的手机和电脑还在使用冯·诺依曼架构吗？今天我们将围绕这些问题展开。

思维导图：

1. 计算机的早期历史

在 1936 年，艾伦·图灵在论文《论可计算数及其在可判定性问题上的应用》中开创性地提出了计算机的通用逻辑模型 —— 图灵机模型。这一理论深刻地影响了第一代计算机科学家，更多能够实现计算功能的计算机被制造出来，图灵也因此被誉为 “计算机科学之父”。

随着计算机的元器件从继电器升级到电子管（也叫真空管），计算机也从 “机电” 时代进入到 “电子” 时代。第一台电子计算机一般认为是 ABC（ Atanasoff-Berry Computer），然而它与其他早期的计算机一样，都是 不可重新编程 的（参考资料上的用词是 “不可编程”，我认为 “不可重新编程” 更恰当）。一台计算机只能执行一个特定的程序，如果需要修改程序功能，就需要将整个计算器拆开，然后重新组装电路。

到了 1943 年，Colossus Mark I 计算机（巨人 1 号）在英国 Bletchley 公园（二战时的密码破译机构）被建造出来，以破解纳粹通信，好家伙一口气造了 10 台。 Colossus Mark I 被认为是第一台可编程的电子计算机，编程方法就是使用大量的开关和插线板（PlugBoards）。 但 Colossus Mark I 并不是通用计算机，它只被设计用于执行密码分析相关的计算。

Colossus Mark I

—— 图片引用自 Wikipedia

直到 1945 年，John Mauchly 和 J. Presper Eckert 在美国宾夕法尼亚大学建造了 ENIAC（Electronic Numerical Integrator and Computer，中译：埃尼亚克）， ENIAC 被认为是第一台可编程的通用电子计算机，也被认为是第一台现代意义上的计算机。 但是，ENIAC 和 Colossus Mark I 一样都使用插线板编程，虽然不需要拆掉整台计算机来重新编程，但是编程效率依然非常低，据说一个简单程序在 ENIAC 上编程最多要花费三个星期。

这对于早期异常昂贵的计算机来说，需要停机这么长时间来重新编程是无法接受的。人们迫切需要一种更高效更灵活的编程方式，有人开始研究 使用存储器来保存程序和程序处理的数据。 在 1944 年，ENIAC 的发明者之一 J. Presper Eckert 发明了一种基于水银管的存储器，这为后来的存储程序概念提供了实现基础。

ENIAC

—— 图片引用自 Wikipedia

在建造 ENIAC 的同时，Mauchly 和 Eckert 也在同步研究一种新设计 EDVAC，并向 John von Neumann（冯·诺依曼）提出咨询。冯·诺依曼也参与到 EDVAC 项目中，并且写了一份著名的内部文档 《First Draft of a Report on the EDVAC》 ，详细阐述了 “存储程序计算机（Stored-program Computer）” 的概念，这就是后来人们所说的 “冯·诺依曼架构”。

后来，他们在 1947 年对 ENIAC 进行诸多改进，ENIAC 也成为了世界上第一台存储程序计算机。而 1948 年建造完成的 Manchester Baby 则被认为是世界上第一台基于冯·诺依曼架构的通用计算机。从 Baby 到现在 70 多年的时间，所有的单片机、PC 电脑、智能手机、服务器依然在遵循这一计算机架构。 现代所有的计算机科学上的发展都是在软件和硬件能力上做优化，根本上的计算机架构依然没有改变。 冯·诺依曼也因而被誉为 “电子计算机之父”。

2. 冯·诺依曼架构 —— 电子计算机的实现结构

2.1 什么是冯·诺依曼架构？

冯·诺依曼架构（Von Neumann Architecture） 是冯·诺依曼和其他人提出的电子计算机通用架构。冯·诺依曼架构将通用计算机定义为以下 3 个基本原则：

• 1、采用二进制： 指令和数据均采用二进制格式；
• 2、存储程序： 一个计算机程序，不可能只有一条指令，而是由成千上万条指令组成的。指令和数据均存储在存储器中，而不是早期的插线板中，计算机按需从存储器中取指令和取数据；
• 3、计算机由 5 个硬件组成： 运算器、控制器、存储器、输入设备和输出设备。在最开始的计算机中，五个部件是围绕着运算器运转的，这使得存储器和 I/O 设备之间的数据传送也需要经过运算器。 而现代计算机中，五个部件是围绕着存储器运转的，这使得存储器和 I/O 设备可以直接完成数据传送，而不需要经过 CPU。

冯·诺依曼架构

—— 图片引用自 Wikepedia

在冯·诺依曼架构之前还有一个哈佛架构，现在说的比较少。两者的区别在于冯·诺依曼是将指令和数据存储在同一个存储器的不同位置，存在争用问题；而哈弗架构将指令和数据存储在不同存储器中，规避了争用问题，与 CPU L1 缓存将指令和数据分离的思想类似。

2.2 冯·诺依曼瓶颈

冯·诺依曼瓶颈的概念最早由 John Backus 在 1977 年的图灵奖领奖演讲中提出： 由于 CPU 和存储器之间共享同一个系统总线，并且 CPU 和存储器之间存在巨大的速度差，导致 CPU 需要不断地被迫等待数据读取或写入到存储器，因此遏制了 CPU 的吞吐量 （关于总线系统，我们后面会专门讲）。

要从根本上解决冯·诺依曼瓶颈，还是只能重新构建一套新的计算机体系，例如生物计算机、量子计算机。不过，目前它们都还处在非常原始的阶段。现代计算机体系只能采用优化策略来减弱冯·诺依曼瓶颈的影响，这些内容我们后面都会提到，例如：

• 1、增加一个位于 CPU 和主内存之间的高速缓存
• 2、将指令缓存和数据缓存分离
• 3、CPU 分支预测
• 4、将存储器集成到 CPU 芯片内部，以减少内存访问（SoC 芯片）

相关文章：

• 计算机系统 #6 计算机的存储器金字塔长什么样？
• 计算机系统 #8 我把 CPU 三级缓存的秘密，藏在这 8 张图里

3. 总结

如果说图灵机描述的是计算机的抽象模型，那么冯·诺依曼架构则是对图灵机这个抽象模型的实现架构。 冯诺依曼架构确立了现代电子计算机的基础和结构，学习计算机组成原理，其实就是学习和拆解冯诺依曼架构。计算机组成原理怎么学，我们下回说。关注我，带你了解更多。

参考资料

• Von Neumann architecture —— Wikipedia
• Von Neumann Bottleneck —— Wikipedia
• Harvard Architecture —— Wikipedia
• Stored-program Computer —— Wikipedia
• EDVAC —— Wikipedia
• EDIAC —— Wikipedia
• Delay-line memory —— Wikipedia
• Colossus Computer —— Wikipedia
• Manchester Baby —— Wikipedia

推荐阅读

计算机系统系列完整目录如下（2023/07/11 更新）：

• #1 从图灵机到量子计算机，计算机可以解决所有问题吗？
• #2 一套用了 70 多年的计算机架构 —— 冯·诺依曼架构
• #3 为什么计算机中的负数要用补码表示？
• #4 今天一次把 Unicode 和 UTF-8 说清楚
• #5 为什么浮点数运算不精确？（阿里笔试）
• #6 计算机的存储器金字塔长什么样？
• #7 程序员学习 CPU 有什么用？
• #8 我把 CPU 三级缓存的秘密，藏在这 8 张图里
• #9 图解计算机内部的高速公路 —— 总线系统
• #10 12 张图看懂 CPU 缓存一致性与 MESI 协议，真的一致吗？
• #11 已经有 MESI 协议，为什么还需要 volatile 关键字？
• #12 什么是伪共享，如何避免？

⭐️ 永远相信美好的事情即将发生，欢迎加入小彭的 Android 交流社群~

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。

计算机系统是程序员的知识体系中最基础的理论知识，你越早掌握这些知识，你就能越早享受知识带来的 “复利效应”。

本文是计算机系统系列的第 1 篇文章，完整文章目录请移步到文章末尾~

前言

大家好，我是小彭。

今天，我们正式开启一个新专栏 —— 计算机组成原理。 计算机组成原理是计算机科学中最基础的理论知识，你越早掌握这些知识，你就能越早享受知识带来的 “复利效应”。

在构思到写作的过程中，我一直在思考应该以什么内容作为这个专栏的开篇，应该以什么内容来吸引住读者的眼球，也有过其它一些想法。最后，我决定抛开所有功利的想法，回归到一个最纯粹的计算机科学问题 —— “计算机可以解决所有问题吗？”。

思维导图：

1. 图灵机 —— 哪些问题是可计算的？

一个有纸、笔、橡皮擦并且坚持严格的行为准则的人，实质上就是一台通用图灵机。 —— 图灵

1.1 图灵机的背景

在计算机科学中， 可计算性（calculability） 是指一个问题是否存在解决算法。对于一个问题，如果能够使用有限的机械的步骤求出结果，就是可计算的，反之则认为这个问题是不可计算的。

一开始，人们普遍认为任何问题都是有算法的，都是可计算的，而科学家的工作正是找出这些问题的解决算法。后来，人们经过长时间研究，发现很多问题依然找不到算法，也无法做出不存在算法的证明。例如数学家希尔伯特提出的 23 个数学问题中的第 10 个问题：

• 希尔伯特第 10 问题： 是否存在一个算法能判定任何丢番图方程有无整数解？

这个问题其实是希尔伯特提出的另一个问题的子集：

• 可判定性问题： 是否存在一个算法能够判定任何数学命题的真伪？ 如果存在这样的算法，那么很多数学问题都可以直接得到答案。如果不存在这样的算法，希尔伯特第 10 问题自然也不成立。

在图灵之前，美国数学家阿隆佐·丘奇（图灵的导师）率先提出了可判定性问题的解决方法 —— Lambda 演算 数学表达系统，并证明了不存在这样的通用判定算法，但其使用了非常多的数学技巧，难以理解和应用。

直到 1936 年（小伙子才 24 岁！），英国科学家艾伦·图灵在数学杂志上发表了论文 《论可计算数及其在可判定性问题上的应用》 ，其中提出了解决 “可判定性问题” 的一个开创性思路。论文我看不懂，我尽量将自己能理解到的核心思路概括为 3 点，如果有错误，欢迎你帮我指出：

• 1、自动机（Automatic Machines）： 图灵观察了人类使用笔和橡皮擦在纸上进行计算的过程，将现实世界中的所有计算行为归结为一系列简单机械的动作。在论文中，图灵将这种以简单机械的方式运行的想象中的机器称为自动机，而后人则将这种机器称为 “图灵机”；同时，图灵证明了只要提供足够的时间和内存，图灵机总是能够实现任何计算；
• 2、通用图灵机（Universal Turing Machines）： 假设有一个特殊的图灵机，它能够接收另外一些图灵机作为输入，并且能够产生和这些图灵机一样的输出，那么我们说这个特殊的图灵机就是通用图灵机。 在这里，我们可以把图灵机想象成一个程序或一个算法，而通用图灵机就是能够运行程序的计算机，目前我们所能接触到的所有现代电子计算机都是通用图灵机。
• 3、停机问题（Halting Problem）： 为了解决希尔伯特的可判定性问题，图灵将 “判定数学命题真伪” 的问题转化为 “判定图灵机是否会停机” 的问题，即著名的停机问题 —— “是否存在一个能够判定其它图灵机是否会停机的通用图灵机”。 随后，图灵通过一个巧妙的逻辑矛盾证明了不存在这样的通用图灵机，等于证明了 “不存在一个算法能够判定任何数学命题的真伪”。图灵的这个逻辑证明的推导过程，我们先放到一方稍后再说。

小结一下： 图灵首先提出了一个能够实现任何计算的计算机模型 —— 图灵机，相比于阿隆佐·丘奇提出 Lambda 演算系统，图灵机模型更加简单。随后，图灵提出了著名的停机问题，并通过巧妙的逻辑悖论证明了停机问题在图灵机上是不可计算的，这是最早被证明无法解决的可判定性问题之一，为希尔伯特的可判定性问题提供了一个反例论证。

图灵雕像

—— 图片引用自 Wikipedia

1.2 图灵机的工作原理

图灵机的工作原理与人类使用笔和橡皮擦在纸上进行计算的过程类似，图灵机主要由 4 个部分组成：

• 1、输入：一条无限长的纸带 TAPE，纸带上写满连续的符号，类似于计算机的指令；
• 2、读写头 HEAD ：一个可移动指针，可以从纸袋上读取符号；
• 3、符号表 TABLE ：规定了图灵机在不同状态下遇到不同符号的处理规则；
• 4、状态寄存器：记录图灵机内部状态（有限状态），其中有一个特殊的停机状态（HALT），当图灵机遇到停机状态时，程序结束。

图灵机示意图

—— 图片引用自 Wikipedia

在计算过程中，图灵机的读写头从纸带头部开始，不断地读取纸袋上的符号。图灵机内部有不同的状态，每个状态会根据读取到的符号，到不同的符号表中查找下一步的动作，例如左移、右移、修改格子或修改寄存器。不断重复这个步骤，最终，当图灵机运行到停机状态时，表示计算完成， 整个计算过程自始至终都由机器自动完成。

图灵机模型

—— 图片引用自 Wikipedia

1.3 停机问题的逻辑证明

停机问题： 是否存在一个计算机程序，它能够根据任意计算机程序的描述和输入来判断该程序最终会停止还是永远运行。如果把图灵机想象成一个程序或一个算法，那么这个问题就等价于：是否存在一个通用图灵机，它能够根据任意图灵机的描述和输入来判定该图灵机最终会停止还是永远运行。

在此之前，先思考一个类似的逻辑悖论：

理发师悖论： 在某个城市中有一位理发师，他的广告词是这样写的：“本人的理发技艺十分高超，我将为本城所有不给自己刮胡子的人刮胡子，我也只给这些人胡子”。来找他刮脸的人络绎不绝，可是，有一天，这位理发师发现自己的胡子长了，他本能地抓起了剃刀，但是他看到自己的广告牌后陷入沉思：如果他不给自己刮胡子，他就属于 “不给自己刮胡子的人”，那么他就该给自己刮胡子。而如果他给自己刮胡子，他就属于 “给自己刮脸的人”，他就不该给自己刮胡子。

那这个理发师到底该不该给自己刮胡子呢？无论他刮还是不刮都会与广告词矛盾，产生一个悖论。唯一的破解方法就是把理发师自己排除到广告词的规则外，这样他想刮还是不刮都可以。

现在，我们回过头来 follow 图灵对停机问题的逻辑证明：

• 1、 假设存在一个能够判定其它程序是否会停机的通用图灵机 H，输出结果是 “会停机 or 不停机”。 如果能够找到一个程序，图灵机 H 无法正确地判断该程序是否会停机，就说明停机问题无法解决；
• 2、 为了找到这样的程序，图灵基于 H 定义了另一个图灵机 ^H，^H 会产生与输入程序相反的输出：如果程序会停机则 ^H 不会停机，如果程序不会停机则 ^H 会停机。
  • 如果 H 的输出结果是 “程序会停机”，那么 ^H 进入一个死循环永远运行下去，即 ^H 不停机；
  • 如果 H 的输出结果是 “程序不停机”，那么 ^H 会输出 “程序不停机”，并且停机。
• 3、现在 H 和 ^H 各司其职，勉强可以理解。 思考一个特殊情况，如果把 ^H 本身作为 ^H 的输入程序，结果是什么？
  • 如果 H 的输出结果是 “^H 会停机”，那么 ^H 会进入死循环永远不停机；
  • 如果 H 的输出结果是 “^H 不停机” ，那么 ^H 会停机。

可以看到，跟理发师悖论类似，H 不管怎么回答都是矛盾的。这一悖论也意味着停机问题不能用图灵机来解决。

停机悖论

1.4 图灵机的意义

我所理解的图灵机的应用价值主要体现在 2 个方面：

• 1、奠定了现代计算机的抽象逻辑模型： 其实，在图灵机模型之前，也有其他科学技术提出了能够描述人类计算能力的模型，例如 Lambda 演算。但相比于其他模型，图灵机模型的优势在于简单直接，而且很容易通过机械技术或电子技术实现。在图灵机模型的价值被世人认可后，图灵机模型也为现代计算机奠定了理论基础。 图灵后来被誉为 “计算机科学之父”，图灵机模型的贡献比重很大。
• 2、证明了计算机存在计算边界： 图灵先是证明了图灵机总是能够实现任何计算，但又证明了停机问题无法用图灵机解决。将这两点结合起来，说明不是所有问题都能用计算解决，例如决策问题。这一理论后来建立了可计算理论的基础，后人称之为 “丘奇-图灵论题” ：无论有多少时间或内存，有些问题是计算机无法解决的，除非建立完全超越图灵机的计算模型，或者说 “超计算”。

目前，量子计算机是计算机科学界最尖端的发展方向，那么量子计算机和我们熟悉的经典计算机有哪些不同呢，量子计算是超运算吗，量子计算机能解决所有问题？

2. 量子计算机 —— 用实验代替计算

2.1 什么是量子计算机？

量子计算机（Quantum computer）一种使用 “量子物理实验代替数学计算” 的计算机。

在 1982 年，诺贝尔物理奖获得者理查德·费曼在报告 《计算机模拟物理学》中最早提出相对成熟的量子计算概念：对于千变万化且初始状态不确定的问题，如果单纯依靠计算难以解决，那么直接用量子实验来模拟，再观察实验的结果来获得计算结果。根据大数定律，只要实验采样的次数足够多，就能以足够大的精度获得结果。举个类似的例子，18 世纪的蒲丰投针实验，就是一种用反复投针的物理实验得到圆周率的方法，也是用实验获得计算结果的案例。

然而，量子计算机依然遵循丘奇-图灵论题，量子计算机在可计算性方面并没有任何优势。 任何可以由量子计算机解决的问题，只要提供足够的时间，都可以由经典计算机解决。虽然如此，量子计算机在处理某些特定问题上会存在时间上的绝对优势，这就是量子优越性。

2.2 什么是量子优越性？

经典计算机和量子计算机解决的问题有一定交叉，但两者擅长的方向不一样。量子计算机在解决特定问题上的绝对优势，也叫量子优越性。 例如，在路径规划、密码破解、材料设计、人工智能，原子结合，基因序列等，只需要知道答案，不需要知道过程的问题上，量子计算机强于经典计算机。那么，量子计算机是如何实现这一优越性的呢？—— 量子比特。

量子计算最基础的单元是 ”量子比特“，与电子比特在同一时刻只能表示 “0” 或 “1” 不同，量子比特既可以是 “0” 或 “1” 其中之一，也可以是 “0” 和 ”1“ 的叠加态。那么，1 个量子比特可以是 2 个电子比特的叠加态，2 个纠缠的量子比特就可以是 4 种电子比特的叠加态，4 个纠缠的量子比特就是 16 种电子比特的叠加态…… 依次类推，nnn 个纠缠的量子比特就是 2n2^n2n 种电子比特的叠加态。

这个特点有什么用呢？举个例子，要寻找 1 亿种密码中的正确密码，经典计算机的解法是用 穷举 法依次尝试 1 亿种可能性，直到出现命中正确答案的结果后停止。 而量子计算机可以直接制造叠加所有可能性的量子比特，一次性尝试所有可能性。 再通过量子干涉操控放大命中正确答案的信号，而缩减错误答案的信号，使得最终量子态包含引起正确答案的信号， 通过观察得到正确答案。

4个相互纠缠的量子比特可以同时处于 16 种比特组合中的所有状态

—— 原图截图自 突破！Fluxonium两比特门精度99.72% —— 阿里达摩院扫地僧 著

2.3 量子计算两大核心难题 —— 多比特 & 高精度

• 多比特数： 目前还未实现超过百级的比特数；
• 高精度： 操控量子的精度不够，且比特数越多，操控难度越大。当操作次数增加后，错误也会累积，最终量子态包含的正确信息也会越少，反而丢失了量子优越性。在现有的量子纠错方案下，维护 1 个物理比特的正确性需要另外 1000 个物理比特来纠错。

3. 总结

今天，我们了解了图灵机模型和量子计算机的简单原理，并在此基础上思考了计算机的计算边界，并不是所有问题都可以用计算解决。 虽然图灵机是所有现代计算机的抽象逻辑模型，但图灵机并不是一个实际的机器。 你应该听过冯·诺依曼机，它跟图灵机一样吗？

参考资料

• Truing machine —— Wikipedia
• Universal Turing Machine —— Wikipedia
• Halting problem —— Wikipedia
• Church–Turing Thesis —— Wikipedia
• Quantum Computing —— Wikipedia
• Qubit —— Wikipedia
• 突破！Fluxonium两比特门精度99.72% —— 阿里达摩院扫地僧 著
• 10分钟速成课 计算机科学（第 15 集 · 艾伦·图灵） —— Carrie Anne 著

推荐阅读

计算机系统系列完整目录如下（2023/07/11 更新）：

• #1 从图灵机到量子计算机，计算机可以解决所有问题吗？
• #2 一套用了 70 多年的计算机架构 —— 冯·诺依曼架构
• #3 为什么计算机中的负数要用补码表示？
• #4 今天一次把 Unicode 和 UTF-8 说清楚
• #5 为什么浮点数运算不精确？（阿里笔试）
• #6 计算机的存储器金字塔长什么样？
• #7 程序员学习 CPU 有什么用？
• #8 我把 CPU 三级缓存的秘密，藏在这 8 张图里
• #9 图解计算机内部的高速公路 —— 总线系统
• #10 12 张图看懂 CPU 缓存一致性与 MESI 协议，真的一致吗？
• #11 已经有 MESI 协议，为什么还需要 volatile 关键字？
• #12 什么是伪共享，如何避免？

⭐️ 永远相信美好的事情即将发生，欢迎加入小彭的 Android 交流社群~

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。

学习数据结构与算法的关键在于掌握问题背后的算法思维框架，你的思考越抽象，它能覆盖的问题域就越广，理解难度也更复杂。在这个专栏里，小彭将基于 Java / Kotlin 语言，为你分享常见的数据结构与算法问题，及其解题框架思路。

本文是数据结构与算法系列的第 10 篇文章，完整文章目录请移步到文章末尾~

前言

大家好，我是小彭。

今天分享到一种非常有趣的数据结构 —— 前缀和数组。前缀和的思想本身很容易理解，同时也是理解更高难度的线段树、字典树等数据结构的基础。

那么，什么是前缀和，我们可以使用前缀和解决什么问题呢？今天我们就围绕这两个问题展开。

思维导图：

1. 什么是前缀和

前缀和数组是一种用来高效地解决 “静态数据的频繁区间和查询” 问题的数据结构。

先举个例子，给定一个整数数组，要求输出数组在 [i,j][i, j][i,j] 区间内元素的总和，这就是区间查询问题。这道题的暴力解法是很容易想到的，无非就是把 [i,j][i, j][i,j] 区间中所有元素累计而已即可，时间复杂度是 O(n)O(n)O(n)，空间复杂度是 O(1)O(1)O(1)。

单次查询确实已经没有优化空间了，但如果进行频繁的区间和查询，很明显会有非常多重复的求和运算。例如，在查询 [1,5][1, 5][1,5] 区间和 [1,10][1, 10][1,10] 区间时，[1,5][1, 5][1,5] 这个子区间就被重复计算了。那么，有可能借助 “空间换时间”，在 O(1)O(1)O(1) 时间复杂度内计算 [5000,1000000][5000,1000000][5000,1000000] 上的区间和吗？

这就需要使用前缀和 + 差分技巧：

• 预处理阶段： 开辟一个前缀和数组，记录每个位置到所有前驱节点的累加和 preSumpreSumpreSum，总共需要 O(n) 时间；
• 查询阶段： 将区间左右端点的区间和相减，就可以在 O(1)O(1)O(1) 时间得到这个区间中所有元素的累加和，避免了每次查询都需要 for 循环遍历整个区间求和。例如，要求 [i,j][i, j][i,j] 区间的和，就是直接用 preSum[j+1]−preSum[i]preSum[j + 1] - preSum[i]preSum[j+1]−preSum[i] 获得。

前缀和示意图

2. 典型例题 · 区间和检索

理解以上概念后，就已经具备解决区间和问题的基本知识了。我们来看一道 LeetCode 上的前缀和典型例题：LeetCode 303. 区域和检索 - 数组不可变

LeetCode 例题

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

kotlin复制代码class NumArray(nums: IntArray) {

    // 前缀和数组
    // 数组长度加一后不用考虑数组越界，代码更简洁
    private val preSum = IntArray(nums.size + 1) { 0 }

    init {
        for (index in nums.indices) {
            preSum[index + 1] = preSum[index] + nums[index]
        }
    }

    fun sumRange(i: Int, j: Int): Int {
        return preSum[j + 1] - preSum[i]
    }
}

代码很简单，其中前缀和数组 preSum 的长度要额外加 1 是为了简化数组越界判断。我们来分析它的复杂度：

• 时间复杂度： 构建前缀和数组的时间复杂度是 O(n)O(n)O(n)，查询的时间复杂度是 O(m)O(m)O(m)，nnn 是数据量，mmm 是区间和查询的次数；
• 空间复杂度： O(n)O(n)O(n)，使用了 长度为 n+1n+ 1n+1 的前缀和数组。

另外，前缀和还适用于二维区间和检索，思路都是类似的，你可以试试看： LeetCode · 304. 二维区域和检索 - 矩阵不可变

3. 典型例题 · 前缀和 + 哈希表

继续看另一道前缀和与哈希表结合的例题：LeetCode 560. 和为 K 的子数组

LeetCode 例题

这道题就是在考前缀和思想，我们可以轻松地写出第一种解法：

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

kotlin复制代码class Solution {
    fun subarraySum(nums: IntArray, k: Int): Int {
        // 1、预处理：构造前缀和数组
        var preSum = IntArray(nums.size + 1) { 0 }
        for (index in nums.indices) {
            preSum[index + 1] = preSum[index] + nums[index]
        }

        // 2、枚举所有子数组，使用「前缀和 + 差分」技巧计算区间和
        var result = 0
        for (i in nums.indices) {
            for (j in i until nums.size) {
                val sum_i_j = preSum[j + 1] - preSum[i]
                if (k == sum_i_j) {
                    result++
                }
            }
        }
        return result
    }
}

在这个题解中，我们枚举每个子数组，使用「前缀和 + 差分」技巧计算区间和为 K 的个数，我们来分析下它的复杂度：

• 时间复杂度： 一共存在 n2n^2n2 个子数组，单次子数组的区间查询是 O(1)O(1)O(1)，所以整体的时间复杂度是 O(n2)O(n^2)O(n2)；
• 空间复杂度： O(n)O(n)O(n)。

时间复杂度有办法优化吗？我们发现，题目要求的是数组个数，而不关心具体的数组，所以我们不必枚举全部子数组（一共有 n2n^2n2 个子数组）， 我们只需要在计算出当前位置的前缀和之后，观察之前的位置中是否存在前缀和正好等于 preSum[j]−KpreSum[j] - KpreSum[j]−K 的位置，有的话，就说明它们之间的区间和就是 KKK。 把满足条件的个数累加起来，就是最终结果。

前缀和示意图

紧接着另一个问题是：怎么快速找到前缀和等于 preSum[j]−KpreSum[j] - KpreSum[j]−K 的位置？聪明的你一定知道了—— 哈希表。 我们可以维护一个哈希表，记录前缀和出现的位置，就可以用 O(1) 找到它。 由于前缀和有可能会重复出现，而且我们只关心次数不关心位置，所以映射关系应该为 <前缀和 - 出现次数>。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

kotlin复制代码class Solution {
    fun subarraySum(nums: IntArray, k: Int): Int {
        var preSum = 0
        var result = 0

        // 维护哈希表<前缀和，出现次数>
        val map = HashMap<Int, Int>()
        map[0] = 1

        for (index in nums.indices) {
            preSum += nums[index]
            // 获得前缀和为 preSum - k 的出现次数
            val offset = preSum - k
            if (map.contains(offset)) {
                result += map[offset]!!
            }
            map[preSum] = map.getOrDefault(preSum, 0) + 1
        }
        return result
    }
}

我们来分析下它的复杂度：

• 时间复杂度： 每个元素只处理一次，整体时间复杂度是 O(n)O(n)O(n)；
• 空间复杂度： O(n)O(n)O(n)。

4. 典型例题 · 前缀和 + 单调队列

继续看一道前缀和与单调队列结合的例题，你可以先做一下第 53 题：

• LeetCode 53. 最大子数组和
• LeetCode 918. 环形子数组的最大和

LeetCode 例题

在第 53 题中，我们只需要维护一个当前观察到的最小前缀和变量，将其与当前的前缀和做差值，就可以得到以当前节点为右端点的最大的区间和。这一题就是考前缀和思想，相对简单。

第 53 题题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

kotlin复制代码class Solution {
    fun maxSubArray(nums: IntArray): Int {
        // 前缀和 + 单调：维护最小的前缀和
        var minPreSum = 0
        var result = Integer.MIN_VALUE
        var preSum = 0

        for (element in nums) {
            preSum += element
            result = Math.max(result, preSum - minPreSum)
            minPreSum = Math.min(minPreSum, preSum)
        }
        return result
    }
}

在第 918 题中，数组变为环形数组，环形数组的问题一般都会用 2 倍的 “假数据长度” 做模拟，求前缀和数组这一步大同小异。

关键在于： “子数组最多只能包含固定缓冲区 num 中的每个元素一次”，这意味随着观察的区间右节点逐渐向右移动，所允许的左区间会限制在一个滑动窗口范围内，以避免元素重复出现。因此，一个变量不再能够满足题目需求。

示意图

所以我们的问题就是要求这个 “滑动窗口中的最小前缀和”。Wait a minute! 滑动窗口的最小值？这不就是 数据结构与算法 #12 使用单调队列解决 “滑动窗口最大值” 问题 这篇文章讲的内容吗，秒懂，单调队列安排一下。

第 918 题题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

kotlin复制代码class Solution {
    fun maxSubarraySumCircular(nums: IntArray): Int {
        val preSum = IntArray(nums.size * 2 + 1).apply {
            for (index in 0 until nums.size * 2) {
                this[index + 1] = this[index] + nums[index % nums.size]
            }
        }

        // 单调队列（从队头到队尾递增）
        val queue = LinkedList<Int>()
        var result = Integer.MIN_VALUE

        for (index in 1 until preSum.size) {
            // if：移除队头超出滑动窗口范围的元素
            // 前缀和窗口 k 为 length + 1，比原数组上的逻辑窗口大 1 位，因为区间的差值要找前一个节点的前缀和
            if (!queue.isEmpty() && queue.peekFirst() < index - nums.size /* index - k + 1 */) {
                queue.pollFirst()
            }

            // 从队头取目标元素
            result = Math.max(result, preSum[index] - (preSum[queue.peekFirst() ?: 0]))

            // while：队尾元素大于当前元素，说明队尾元素不再可能是最小值，后续不再考虑它
            while (!queue.isEmpty() && preSum[queue.peekLast()] >= preSum[index]) {
                // 抛弃队尾元素
                queue.pollLast()
            }
            queue.offerLast(index)
        }
        return result
    }
}

我们来分析它的时间复杂度：

• 时间复杂度： 构建前缀和数组 O(n)O(n)O(n)，前缀和数组中每个元素在单调队列中入队和出队 111 次，因此整体时间复杂度是 O(n)O(n)O(n);
• 空间复杂度： 构建前缀和数组 O(n)O(n)O(n)，最坏情况下（递减序列）所有元素都被添加到单调队列中，因此整体空间复杂度是 O(n)O(n)O(n)。

提示： 这道题还有使用 Kadane 算法 的 O(1)O(1)O(1) 空间复杂度解法。

5. 总结

到这里，前缀和的内容就讲完了。文章开头也提到了， 前缀和数组是一种高效地解决静态数据的频繁区间和查询问题的数据结构，只需要构造一次前缀和数组，就能使用 O(1) 时间完成查询操作。

那么，在动态数据的场景中（即动态增加或删除元素），使用前缀和数组进行区间和查询是否还保持高效呢？如果不够高效，有其他的数据结构可以解决吗？你可以思考以下 2 道题：

• LeetCode · 307. 区域和检索 - 数组可修改
• LeetCode · 308. 二维区域和检索 - 矩阵不可变

更多同类型题目：

版权声明

本文为稀土掘金技术社区首发签约文章，14天内禁止转载，14天后未获授权禁止转载，侵权必究！

参考资料

• LeetCode 专题 · 前缀和 —— LeetCode 出品
• LeetCode 题解 · 560. 和为 K 的子数组 —— liweiwei1419 著
• 小而美的算法技巧：前缀和数组 —— labuladong 著
• 小而美的算法技巧：差分数组 —— labuladong 著

推荐阅读

数据结构与算法系列完整目录如下（2023/07/11 更新）：

• #1 链表问题总结
• #2 链表相交 & 成环问题总结
• #3 计算器与逆波兰表达式总结
• #4 高楼丢鸡蛋问题总结
• #5 为什么你学不会递归？谈谈我的经验
• #6 回溯算法解题框架总结
• #7 下次面试遇到二分查找，别再写错了
• #8 什么是二叉树？
• #9 什么是二叉堆 & Top K 问题
• #10 使用前缀和数组解决 “区间和查询” 问题
• #11 面试遇到线段树，已经这么卷了吗？
• #12 使用单调队列解决 “滑动窗口最大值” 问题
• #13 使用单调栈解决 “下一个更大元素” 问题
• #14 使用并查集解决 “朋友圈” 问题
• #15 如何实现一个优秀的 HashTable 散列表
• #16 简答一波 HashMap 常见面试题
• #17 二叉树高频题型汇总
• #18 下跳棋，极富想象力的同向双指针模拟

Java & Android 集合框架系列文章: 跳转阅读

LeetCode 上分之旅系列文章：跳转阅读

⭐️ 永远相信美好的事情即将发生，欢迎加入小彭的 Android 交流社群~

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

本文为稀土掘金技术社区首发签约文章，14天内禁止转载，14天后未获授权禁止转载，侵权必究！

摘要

专栏上一篇文章《Three.js 进阶之旅：基础入门（上）》主要讲解了 Three.js 环境搭建和项目构建及基本开发流程。本篇文章将继续通过一个简单 3D 创意页面的开发，简要汇总一下必备的 Three.js 的基础知识，梳理要点，为后续页面的开发打下坚实的基础。通过本文的内容，你将获得的知识包括：OrbitControls 镜头轨道控制器的使用、Scene.Fog 场景雾化、Three.js 中的光源、几何体、材质、模型、贴图、动画等。

效果

先来看看本节内容示例的实现效果，整个页面是一个由三维几何体构成的简单 🌌 宇宙背景，可以通过鼠标 🖱 操作星空，其中星球、轨道、卫星以及远处的星星 🪐 都在按照既定的动画规则持续转动。

项目托管在 Github 仓库【threejs-odessey】，后续所有专栏项目目录都将在这个仓库中更新。

🔗 代码仓库地址：git@github.com:dragonir/threejs-ode…

码上掘金

实现

页面结构

本页面同样没有额外的元素，只需在 body 中添加一个类名为 .webgl 的 canvas 容器即可，用于渲染三维场景。

1

html复制代码<canvas class="webgl"></canvas>

资源引入

引入 样式表 和 Three.js，除此之外，本页面额外引入了 OrbitControls，它是镜头轨道控制器。

1
2
3

js复制代码import './style.css';
import * as THREE from 'three';
import { OrbitControls } from 'three/examples/jsm/controls/OrbitControls';

渲染场景初始化

场景渲染初始化也基本和上篇内容一样的。值得注意的是，本文中通过 scene.background 给场景设置了一个深黑色背景，通过 scene.fog 给场景设置了雾化效果，场景缩小到一定程度时页面就会叠加一种雾气一样的效果，场景中的物体会逐渐变得模糊。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

js复制代码// 定义渲染尺寸
const sizes = {
  width: window.innerWidth,
  height: window.innerHeight
}

// 初始化渲染器
const canvas = document.querySelector('canvas.webgl');
const renderer = new THREE.WebGLRenderer({ canvas: canvas });
renderer.setSize(sizes.width, sizes.height);
renderer.setPixelRatio(Math.min(window.devicePixelRatio, 2));

// 初始化场景
const scene = new THREE.Scene();
scene.background = new THREE.Color(0x1A1A1A);
scene.fog = new THREE.Fog(0x1A1A1A, 1, 1000);

// 初始化相机
const camera = new THREE.PerspectiveCamera(40, sizes.width / sizes.height)
scene.add(camera);
camera.position.set(20, 100, 450);

// 页面缩放事件监听
window.addEventListener('resize', () => {
  sizes.width = window.innerWidth;
  sizes.height = window.innerHeight;
  // 更新渲染
  renderer.setSize(sizes.width, sizes.height);
  renderer.setPixelRatio(Math.min(window.devicePixelRatio, 2))
  // 更新相机
  camera.aspect = sizes.width / sizes.height;
  camera.updateProjectionMatrix();
});

💡 知识点 Scene.Fog 场景雾化

Fog 类定义的是线性雾，雾的密度随着距离线性增大，即场景中物体雾化效果随着随距离线性变化。

构造函数：

1

js复制代码Fog(color, near, far)

• color: 表示雾的颜色，如设置为白色，场景中远处物体为蓝色，场景中最近处距离物体是自身颜色，最远和最近之间的物体颜色是物体本身颜色和雾颜色的混合效果。
• near：表示应用雾化效果的最小距离，距离活动摄像机长度小于 near 的物体将不会被雾所影响。
• far：表示应用雾化效果的最大距离，距离活动摄像机长度大于 far 的物体将不会被雾所影响。

初始化控制器

初始化镜头轨道控制器 OrbitControls ，通过它可以对三维场景用鼠标 🖱 进行缩放、平移、旋转等操作，本质上改变的不是场景，而是相机的位置参数。可以选择通过设置 controls.enableDamping 为 true 来开启控制器的移动惯性，这样在使用鼠标交互过程中就会感觉更加流畅和逼真。

1
2

js复制代码const controls = new OrbitControls(camera, renderer.domElement);
controls.enableDamping = true;

添加光源

和现实世界一样，没有光线 🌞 的话就什么都看不见。未添加光源之前场景中的所有网格元素都是黑色的，无法显示其颜色和材质表面的物理特性，此时就需要给场景添加光源，才能看见场景中的物体。

本示例中只添加了一种光源 AmbientLight 环境光，它是一种基础光源，整个场景中的物体都将接收它的颜色。其中两个参数分别代表光照的颜色和强度。

1
2

js复制代码const light = new THREE.AmbientLight(0xdeedff, 1.5);
scene.add(light);

💡 知识点 光源 Light

Three.js 中提供了很多种光源，它们可以模拟现实世界中大部分场景的光照效果。光源的使用方法也大致和本文示例中是一样的。下表列出了几种常用的光源，可以根据自己的需求场景分别选择不同的光源。大家可以在实践中把本示例中的环境光 AmbientLight 换成其他效果光源，看看它们生成的有什么区别。

光源的一些通用属性：

• color：光源颜色。
• intensity：光照强度。默认值是 1。
• visible：如果设为 true，该光源就会显示；如果设置为false，光源就会消失。

创建星球

示例页面中所有的模型元素都是采用 Three.js 内置的基础网格模型生成，所以和上篇文章创建立方体的流程是一样的，先创建立方体和材质，再用它们生成网格模型，最后将它添加到场景中即可。星球模型使用了非光泽表面材质 MeshLambertMaterial，立方体采用 SphereGeometry 生成。

1
2
3
4
5
6
7

js复制代码const SphereMaterial = new THREE.MeshLambertMaterial({
  color: 0x03c03c,
  wireframe: true,
});
const SphereGeometry = new THREE.SphereGeometry(80, 32, 32);
const planet = new THREE.Mesh(SphereGeometry, SphereMaterial);
scene.add(planet);

为材质设置 wireframe: true 属性就能得到几何模型的线框结构，是不是看起来更加有科技感。

💡 知识点 几何体 Geometry

下面汇总了 Three.js 常用几何体的分类介绍以及构造器的参数，后续使用过程中可通过此表查询。由于本文篇幅内容有限，就不一一展示具体形状，大家在学习过程中一定要亲自动手试试各种几何体创建后是什么样子的，也可以多看看 threejs.org 官网文档。

💡 知识点 材质 Material

材质可以模拟现实世界中物体表面的物理特性，Three.js 也提供的丰富的材质，我们在创建不同物体时可以选择不同的材质，比如创建木制桌面时可以选择 MeshPhysicalMaterial 物理网格材质，创建卡通风格模型时可以选择 MeshToonMaterial 卡通网格材质。下表列出了几种常用的材质类型及其说明。

创建星球轨道环

使用上述同样的方法，选择 圆环几何体 TorusGeometry 添加星球轨道到场景中，通过调整它的 rotation 属性来设置倾斜角度。

1
2
3
4
5
6
7
8
9

js复制代码const TorusGeometry = new THREE.TorusGeometry(150, 8, 2, 120);
const TorusMaterial = new THREE.MeshLambertMaterial({
  color: 0x40a9ff,
  wireframe: true
});
const ring = new THREE.Mesh(TorusGeometry, TorusMaterial);
ring.rotation.x = Math.PI / 2;
ring.rotation.y = -0.1 * (Math.PI / 2);
scene.add(ring);

创建卫星

应用 二十面几何体 IcosahedronGeometry 创建一个卫星。

1
2
3
4

js复制代码const IcoGeometry = new THREE.IcosahedronGeometry(16, 0);
const IcoMaterial = new THREE.MeshToonMaterial({ color: 0xfffc00 });
const satellite = new THREE.Mesh(IcoGeometry, IcoMaterial);
scene.add(satellite);

创建星星

我们计划创建 500 个星星 🌟，由于数量较多，每个都单独放置到场景中不仅会造成页面性能问题，而且也不好对星星整体进行管理。为了解决这个问题，我们可以先创建一个 Group，然后将单个星星添加到 Group 分组中，最后再将整个分组添加到场景中。在 for 循环 中创建单个星星时，同样使用的是 IcosahedronGeometry 二十面几何体，材质使用了 MeshToonMaterial 卡通网格材质，并为它们设置了限定范围内的随机位置和角度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

js复制代码const stars = new THREE.Group();
for (let i = 0; i < 500; i++) {
  const geometry = new THREE.IcosahedronGeometry(Math.random() * 2, 0);
  const material = new THREE.MeshToonMaterial({ color: 0xeeeeee });
  const mesh = new THREE.Mesh(geometry, material);
  mesh.position.x = (Math.random() - 0.5) * 700;
  mesh.position.y = (Math.random() - 0.5) * 700;
  mesh.position.z = (Math.random() - 0.5) * 700;
  mesh.rotation.x = Math.random() * 2 * Math.PI;
  mesh.rotation.y = Math.random() * 2 * Math.PI;
  mesh.rotation.z = Math.random() * 2 * Math.PI;
  stars.add(mesh);
}
scene.add(stars);

动画更新

最后除了需要在页面重绘动画中更新相机和渲染器之外，在这里也给场景中的其他物体添加一些动画效果。🪐 星球和轨道朝两个相反的方向自转，卫星 🛰 绕着它们公转。整个星星 Group 也在进行一个同时绕着 Y轴 和 Z轴 的自转。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

js复制代码let rot = 0;
// 动画
const axis = new THREE.Vector3(0, 0, 1);
const tick = () => {
  // 更新渲染器
  renderer.render(scene, camera);
  // 给网格模型添加一个转动动画
  rot += Math.random() * 0.8;
  const radian = (rot * Math.PI) / 180;
  // 星球位置动画
  planet && (planet.rotation.y += .005);
  // 星球轨道环位置动画
  ring && ring.rotateOnAxis(axis, Math.PI / 400);
  // 卫星位置动画
  satellite.position.x = 250 * Math.sin(radian);
  satellite.position.y = 100 * Math.cos(radian);
  satellite.position.z = -100 * Math.cos(radian);
  satellite.rotation.x += 0.005;
  satellite.rotation.y += 0.005;
  satellite.rotation.z -= 0.005;
  // 星星动画
  stars.rotation.y += 0.0009;
  stars.rotation.z -= 0.0003;
  // 更新控制器
  controls.update();
  // 页面重绘时调用自身
  window.requestAnimationFrame(tick);
}
tick();

到此，本文页面的所有功能都全部完成了，如果对 Three.js 以及本文内容实现的页面效果比较感兴趣一定要亲自动手试试。

其他必备知识

下面列出了几个本文示例中未涉及，但是非常重要的几个 Three.js 基础知识，在后续开发中几乎都会用到，也需要牢牢掌握。

模型

在现实开发中，有时除了需要用代码创建模型之外，多数场景需要加载设计师提供的使用设计软件导出的模型。此时就需要使用模型加载器去加载模型，不同格式的模型需要引入对应的模型加载器，虽然加载器不同，但是使用方式基本上是相同的。下面就是使用 OBJLoader 加载 .obj 格式模型的过程。

1
2
3
4
5
6
7
8
9

js复制代码var loader = new THREE.OBJLoader();
loader.load(model, function (object) {
  object.traverse(function (child) {
    if (child.isMesh) {
      // 对模型子网格的一些操作
    }
  });
  scene.add(object);
});

📌 Three.js 支持的模型格式：3ds (.3ds)、amf (.amf)、3mf (.3mf)、assimp & assimp2json (.assimp |.json)、awd (.awd)、Babylon (.babylon)、BVH (.bvh)、Collada(.dae |.xml)、OpenCTM (.ctm)、draco(.drc)、FBX(.fbx)、GCode (.gcode)、glTF (.gltf)、Clara(.json)、KMZ(.kmz)、LDraw(.mpd)、LightWave(.lwo)、MD2 (.md2)、MMD(.pmd | .vmd)、nrrd (.nrrd)、obj/obj2 (.obj)、pcd (.pcd)、PDB(.pdb)、PlayCanvas(.json)、ply (.ply)、prwm(.prwm)、sea3d(.sea3d)、stl(.stl)、vrm(.vrm)、vrml(.vrml)、vtk、x等。

贴图

为了模拟更加真实的效果，就要给模型材质添加贴图，贴图就像模型的皮肤一样，使其三维效果更佳。添加贴图的原理是通过纹理贴图加载器 TextureLoader() 去新创建一个贴图对象出来，然后再去调用里面的 load() 方法去加载一张图片，这样就会返回一个纹理对象，纹理对象可以作为模型材质颜色贴图 map 属性的值，材质的颜色贴图属性 map 设置后，模型会从纹理贴图上采集像素值。下面列出了几种常用的贴图类型以及加载贴图的基本流程。

• map：材质贴图
• normalMap：法线贴图
• bumpMap：凹凸贴图
• envMap：环境贴图
• specularMap：高光贴图
• lightMap：光照贴图

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12

js复制代码const texLoader = new THREE.TextureLoader();
loader.load('assets/models/meta.fbx', function (mesh) {
  mesh.traverse(function (child) {
    if (child.isMesh) {
      if (child.name === '需要添加贴图的模型') {
        child.material = new THREE.MeshPhysicalMaterial({
          map: texLoader.load("./assets/images/metal.png"),
        });
      }
    }
  });
})

动画

给三维场景添加动画可以使得页面变得更加生动，像本例中就给模型添加了简单的基础动画和相机控制动画。Three.js 中的动画基本可以分为下面几类，在本专栏后后续内容中会专门使用一篇内容详细讲解 Three.js 中的动画。

• 基础动画
• 相机控制
• 变形动画
• 用骨骼和蒙皮制作动画
• 使用外部模型创建动画

其他

最后还有着色器和后期渲染、媒体交互、物体特性等高级功能，专栏后续文章将专门讲解这几项相对复杂的内容。

🔗 源码仓库地址：github.com/dragonir/th…

总结

本文中主要包含的知识点包括：

• OrbitControls：镜头轨道控制器的使用
• Scene.Fog 场景雾化
• Three.js 中的光源
• Three.js 中的几何体
• Three.js 中的材质
• Three.js 中的模型
• Three.js 中的贴图
• Three.js 中的动画

想了解其他前端知识或其他未在本文中详细描述的Web 3D开发技术相关知识，可阅读我往期的文章。如果有疑问可以在评论中留言，如果觉得文章对你有帮助，不要忘了一键三连哦 👍。

附录

• 【Three.js 进阶之旅】系列专栏
• [1]. 🌴 Three.js 打造缤纷夏日3D梦中情岛
• [2]. 🔥 Three.js 实现炫酷的赛博朋克风格3D数字地球大屏
• [3]. 🐼 Three.js 实现2022冬奥主题3D趣味页面，含冰墩墩
• [4]. 🦊 Three.js 实现3D开放世界小游戏：阿狸的多元宇宙
• [5]. 🏆 掘金1000粉！使用Three.js实现一个创意纪念页面
• ...
• 更多往期【3D】专栏访问 👈
• 更多往期【前端】专栏访问 👈

参考

• threejs.org/

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。

学习数据结构与算法的关键在于掌握问题背后的算法思维框架，你的思考越抽象，它能覆盖的问题域就越广，理解难度也更复杂。在这个专栏里，小彭将基于 Java / Kotlin 语言，为你分享常见的数据结构与算法问题，及其解题框架思路。

本文是数据结构与算法系列的第 5 篇文章，完整文章目录请移步到文章末尾~

前言

大家好，我是小彭。

今天分享到计算机科学中一个基础又非常重要的概念 —— 递归。递归是计算机中特有的概念，你很难在现实世界中找到一个恰当的例子与之关联起来。因此，对于很多初学编程的人，一开始会很难理解。

那么，究竟什么是递归，我们为什么要使用递归？我们今天就围绕这两个问题展开。

思维导图：

1. 什么是递归？

递归（Recursion）是一种通过 “函数自己调用自己” 的方式，将问题重复地分解为同类子问题，并最终解决问题的编程技巧。

举个例子，要求一个数 nnn 的阶乘 n!=n∗(n−1)∗(n−2)∗…∗2∗1n! = n*(n-1)*(n-2)*…*2*1n!=n∗(n−1)∗(n−2)∗…∗2∗1 ，有 2 种思考问题的思路：

• 递推（一般思维）： 我们从 111 开始，用 111 乘以 222 得到 2!2!2! 问题的解，用 333 乘以 2!2!2! 得到 3!3!3! 问题的解。依次类推，直到用 nnn 乘以 (n−1)!(n-1)!(n−1)! 得到原问题 n!n!n! 的解。这就是用递推解决问题，这是相对简单直接的思考方式；
• 递归（计算机思维）： 我们把 n!n!n! 的问题拆分为一个 (n−1)!(n-1)!(n−1)! 的问题，如果我们知道 (n−1)!(n-1)!(n−1)! 的解，那么将它乘以 nnn 就可以得出 n!n!n! 的解。以此类推，我们将一个 (n−1)!(n-1)!(n−1)! 的问题拆分为同类型的规模更小的 (n−2)!(n-2)!(n−2)! 子问题，直到拆分到无法拆分，可以直接得出结果 1!1!1! 问题。此时，我们再沿着拆分问题的路径，反向地根据子问题的解求出原问题的解，最终得到原问题 n!n!n! 的结果。这就是用递归解决问题。

求 n!

从这个例子可以看出， 递归其实是在重复地做 2 件事：

• 1、自顶向下拆分问题： 从一个很难直接求出结果的、规模较大的原问题开始，逐渐向下拆分为规模较小的子问题（从 n!n!n! 拆分到 (n−1)!(n-1)!(n−1)!），直到拆分到问题边界时停止拆分，这个拆分的过程就是 “递”（问题边界也叫基准情况或终止条件）；
• 2、自底向上组合结果： 从问题边界开始，逐渐向上传递并组合子问题的解（从 (n−1)!(n-1)!(n−1)! 得到 n!n!n!），直到最终回到原问题获得结果，这个组合的过程就是 “归”。

看到这里你会不会产生一个疑问： 我们直接从问题边界 1!1!1! 一层层自底向上组合结果也可以得到 n!n!n! 的解，自顶向下拆分问题的过程显得没有必要。确实，对于对于这种原问题与子问题只是 “线性” 地减少一个问题规模的情况，确实是这样。但是对于很多稍微复杂一些的问题，原问题与子问题会构成一个树型的 “非线性” 结构，这个时候就适合用递归解决，很难用递推解决。

举个例子， 求斐波那契数列，这个问题同时也是 LeetCode 上的一道典型例题：LeetCode · 509. 斐波那契数：该数列从 111 开始，每一项数字都是前面两项数字的和。

LeetCode 例题

虽然，我们可以利用递推的方式从 F(0)F(0)F(0) 和 F(1)F(1)F(1) 自底向上推导出 F(n)F(n)F(n) 的解，但是这种非线性的方式在编程语言中很难实现，而使用递归的方式自顶向下地解决问题，在编码上是很容易实现的。

当然，这段代码中存在非常多的重复计算，最终使得整个算法的时间复杂度达到惊人的指数级 O(2n)O(2^n)O(2n)。例如在计算 F(5)=F(3)+F(4)F(5)=F(3)+F(4)F(5)=F(3)+F(4) 和 F(6)=F(4)+F(5)F(6)=F(4)+F(5)F(6)=F(4)+F(5) 的时候，F(4)F(4)F(4) 就被重复计算 2 次，这种重复计算完全相同的子问题的情况就叫 重叠子问题 ，以后我们再专门讨论。

用递归解决斐波那契数列

用递归解决（无优化）

1
2
3
4
5
6
7
8
9
10
11
12

kotlin复制代码class Solution {
    fun fib(N: Int): Int {
        if(N == 0){
            return 0
        }
        if(N == 1){
            return 1
        }
        // 拆分问题 + 组合结果
        return fib(N - 1) + fib(N - 2)
    }
}

2. 递归的解题模板

• 1、判断当前状态是否异常，例如数组越界，n < 0 等；
• 2、判断当前状态是否满足终止条件，即达到问题边界，可以直接求出结果；
• 3、递归地拆分问题，缩小问题规模；
• 4、组合子问题的解，结合当前状态得出最终解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

kotlin复制代码fun func(n){
    // 1. 判断是否处于异常条件
    if(/* 异常条件 */){
        return
    }
    // 2. 判断是否满足终止条件（问题边界）
    if(/* 终止条件 */){
        return result
    }
    // 3. 拆分问题
    result1 = func(n1)
    result2 = func(n2)
    ...
    // 4. 组合结果
    return combine(result1, result2, ...)
}

3. 计算机如何实现递归？

递归程序在解决子问题之后，需要沿着拆分问题的路径一层层地原路返回结果，并且后拆分的子问题应该先解决。这个逻辑与栈 “后进先出” 的逻辑完全吻合：

• 拆分问题： 就是一次子问题入栈的过程；
• 组合结果： 就是一次子问题出栈的过程。

事实上，这种出栈和入栈的逻辑，在编程语言中是天然支持的，不需要程序员实现。程序员只需要维护拆分问题和组合问题的逻辑，一次函数自调用和返回的过程就是一次隐式的函数出栈入栈过程。在程序运行时，内存空间中会存在一块维护函数调用的区域，称为 函数调用栈 ，函数的调用与返回过程，就天然对应着一次子问题入栈和出栈的过程：

• 调用函数： 程序会创建一个新的栈帧并压入调用栈的顶部；
• 函数返回： 程序会将当前栈帧从调用栈栈顶弹出，并带着返回值回到上一层栈帧中调用函数的位置。

我们在分析递归算法的空间复杂度时，也必须将隐式的函数调用栈考虑在内。

4. 递归与迭代的区别

递归（Recursion）和迭代（Iteration）都是编程语言中重复执行某一段逻辑的语法。

语法上的区别在于：

• 迭代： 通过迭代器（for/while）重复执行某一段逻辑；
• 递归： 通过函数自调用重复执行函数中的一段逻辑。

核心区别在于解决问题的思路不同：

• 迭代：迭代的思路认为只要从问题边界开始，在所有元素上重复执行相同的逻辑，就可以获得最终问题的解（迭代的思路与递推的思路类似）；
• 递归：递归的思路认为只要将原问题拆分为子问题，在每个子问题上重复执行相同的逻辑，最终组合所有子问题的结果就可以获得最终问题的解。

例如， 在计算 n! 的问题中，递推或迭代的思路是从 1! 开始重复乘以更大的数，最终获得原问题 n! 的解；而递归的思路是将 n! 问题拆分为 (n-1)! 的问题，最终通过 (n-1)! 问题获得原问题 n! 的解。

再举个例子，面试中出现频率非常高的反转链表问题，同时也是 LeetCode 上的一道典型例题：LeetCode 206 · 反转链表。假设链表为 1 → 2 → 3 → 4 → ∅，我们想要把链表反转为 ∅ ← 1 ← 2 ←3 ←4，用迭代和递归的思路是不同的：

• 迭代： 迭代的思路认为，只要重复地在每个节点上处理同一个逻辑，最终就可以得到反转链表，这个逻辑是：“将当前节点的 next 指针指向前一个节点，再将游标指针移动到后一个节点”。
• 递归： 递归的思路认为，只要将反转链表的问题拆分为 “让当前节点的 next 指针指向后面整段子链的反转链表”，在每个子链表上重复执行相同的逻辑，最终就能够获得整个链表反转的结果。

这两个思路用示意图表示如下：

示意图

迭代题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14

kotlin复制代码class Solution {
    fun reverseList(head: ListNode?): ListNode? {
        var cur: ListNode? = head
        var prev: ListNode? = null

        while (null != cur) {
            val tmp = cur.next
            cur.next = prev
            prev = cur
            cur = tmp
        }
        return prev
    }
}

迭代解法复杂度分析：

• 时间复杂度：每个节点扫描一次，时间复杂度为 O(n)O(n)O(n)；
• 空间复杂度：使用了常量级别变量，空间复杂度为 O(1)O(1)O(1)。

递归题解

1
2
3
4
5
6
7
8
9
10
11

kotlin复制代码class Solution {
    fun reverseList(head: ListNode?): ListNode? {
        if(null == head || null == head.next){
            return head
        }
        val newHead = reverseList(head.next)
        head.next.next = head
        head.next = null
        return newHead
    }
}

递归解法复杂度分析：

• 时间复杂度：每个节点扫描一次，时间复杂度为 O(n)O(n)O(n)；
• 空间复杂度：使用了函数调用栈，空间复杂度为 O(n)O(n)O(n)。

理论上认为迭代程序的运行效率会比递归程序更好，并且任何递归程序（不止是尾递归，尾递归只是消除起来相对容易）都可以通过一个栈转化为迭代程序。但是，这种消除递归的做法实际上是以牺牲程序可读性为代价换取的，一般不会为了运行效率而刻意消除递归。

不过，有一种特殊的递归可以被轻松地消除，一些编译器或运行时会自动完成消除工作，不需要程序员手动消除，也不会破坏代码的可读性。

5. 尾递归

在编程语言中，尾调用是指在一个函数的最后返回另一个函数的调用结果。如果尾调用最后调用的是当前函数本身，就是尾递归。为什么我们要专门定义这种特殊的递归形式呢？因为尾递归也是尾调用，而在大多数编程语言中，尾调用可以被轻松地消除 ，这使得程序可以模拟递归的逻辑而又不损失性能，这叫 尾递归优化 / 尾递归消除 。例如，以下 2 段代码实现的功能是相同的，前者是尾递归，而后者是迭代。

尾递归

1
2
3
4
5
6
7
8

kotlin复制代码fun printList(itr : Iterator<*>){
    if(!itr.hasNext()) {
        return
    }
    println(itr.next())
    // 尾递归
    printList(itr)
}

迭代

1
2
3
4
5
6
7
8

kotlin复制代码fun printList(itr : Iterator<*>){
    while(true) {
        if(!itr.hasNext()) {
            return
        }
        println(itr.next())
    }
}

可以看到，使用一个 while 循环和若干变量消除就可以轻松消除尾递归。

6. 总结

到这里，相信你已经对递归的含义以及递归的强大之处有所了解。 递归是计算机科学中特有的解决问题的思路：先通过自顶向下拆分问题，再自底向上组合结果来解决问题。这个思路在编程语言中可以用函数自调用和返回实现，因此递归在编程实现中会显得非常简洁。 正如图灵奖获得者尼克劳斯·维尔特所说：“递归的强大之处在于它允许用户用有限的语句描述无限的对象。因此，在计算机科学中，递归可以被用来描述无限步的运算，尽管描述运算的程序是有限的。”

另外，你会发现 “先拆分问题再合并结果” 的思想与 “分治思想” 相同，那么你认为递归和分治是等价的吗？这个我们下回说。

发现一个 Google 的小彩蛋：在 Google 搜索里搜索 “递归”，提示词里会显示 “您是不是要找：递归”。这就会产生递归的效果的，因为点击提示词 “递归” 后，还是会递归地显示 “您是不是要找：递归”。哈哈，应该是 Google 跟程序员开的小玩笑。

版权声明

本文为稀土掘金技术社区首发签约文章，14天内禁止转载，14天后未获授权禁止转载，侵权必究！

参考资料

• 数据结构与算法分析 · Java 语言描述（第 1 章 · 引论、第 3 章 · 表栈和队列、第 10 章 · 算法设计技巧）—— [美] Mark Allen Weiss 著
• 算法导论（第 4 章 · 分治策略）—— [美] Thomas H. Cormen 等 著
• 算法吧 · 递归 —— liweiwei1419 著
• Recursion (computer science) —— Wikipedia
• Divide-and-conquer algorithm —— Wikipedia
• Iterator —— Wikipedia
• Tail call —— Wikipedia

推荐阅读

数据结构与算法系列完整目录如下（2023/07/11 更新）：

• #1 链表问题总结
• #2 链表相交 & 成环问题总结
• #3 计算器与逆波兰表达式总结
• #4 高楼丢鸡蛋问题总结
• #5 为什么你学不会递归？谈谈我的经验
• #6 回溯算法解题框架总结
• #7 下次面试遇到二分查找，别再写错了
• #8 什么是二叉树？
• #9 什么是二叉堆 & Top K 问题
• #10 使用前缀和数组解决 “区间和查询” 问题
• #11 面试遇到线段树，已经这么卷了吗？
• #12 使用单调队列解决 “滑动窗口最大值” 问题
• #13 使用单调栈解决 “下一个更大元素” 问题
• #14 使用并查集解决 “朋友圈” 问题
• #15 如何实现一个优秀的 HashTable 散列表
• #16 简答一波 HashMap 常见面试题
• #17 二叉树高频题型汇总
• #18 下跳棋，极富想象力的同向双指针模拟

Java & Android 集合框架系列文章: 跳转阅读

LeetCode 上分之旅系列文章：跳转阅读

⭐️ 永远相信美好的事情即将发生，欢迎加入小彭的 Android 交流社群~

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

源码共读前言

为了能帮助到更多对源码感兴趣、想学会看源码、提升自己写作和前端技术能力的同学。 帮助读者夯实基础，查漏补缺，开阔眼界，拓宽视野，知其然知其所以然。

我倾力组织了每周一起学200行左右的源码共读活动。我写有《学习源码整体架构系列》20余篇，走过路过的小伙伴可以点击关注下这个目前是掘金关注数最多的专栏。

欢迎点此扫码加我微信 ruochuan02 交流，参与 源码共读 活动，每周大家一起学习200行左右的源码，共同进步。可以持续关注我@若川。

从易到难推荐学习顺序

活动介绍和顺序具体看这里从易到难推荐学习顺序

提交笔记

提交笔记方式，具体的看这里
简言之：看任务，看辅助文章、看源码，交流讨论，在掘金写笔记，写好后提交到本文评论区。

为了给大家谋福利，另外给大家的文章带来更多阅读量，便于搜索，从2022年3月27日起，笔记可以直接发布在掘金，以《标题自取》标题不限，可以取个好标题，容易被掘金推荐。

笔记文章开头加两句话：

• 本文参加了由公众号@若川视野 发起的每周源码共读活动， 点击了解详情一起参与。
• 这是源码共读的第xx期，链接：xxx。

笔记文章最后，建议写上总结、收获、感受等。

• 开头第一句作用是：方便每月统计评优，掘金赞助送小礼物。顺便帮忙宣传推广，让更多人参与进来，一起学习。
• 开头第二句作用是：加上是多少期，当前任务说明的链接，方便读者知道这是什么活动。

笔记写完后，到当前期活动的文章评论区留言自己的文章和笔记特点。方便大家查阅学习交流讨论。

往期所有笔记存放在语雀讨论区。

任务发布时间

9月5日 - 10月7日。可以按照自己节奏学习，提交笔记即可（不一定要严格按照我规定的时间）。往期共读也可以及时复习，笔记未完成可以继续完成。

语雀本期任务说明链接

语雀有树形菜单，更方便查看，所以也放下语雀的这一期链接

学习任务

• 参考学习我的文章，按照文章只学 release-it 部分（也就是第7小节），非常通用。生成 changelog 、打 tag、自动管理版本号
• juejin.cn/post/712446…
• 最后可以发一个简单的包到 npm 上，作为结果。有能力觉得需要，也可以学我的这篇文章的其他部分。
• npx @ruochuan/mini-ci -v 查看版本
• npx @ruochuan/mini-ci -h 查看帮助信息
• 可以参考我的仓库，我是如何发布包的~
• github.com/lxchuan12/m…
• 还可以参考这篇文章：图文结合简单易学的npm 包的发布流程

参考文章

• 看文章，看源码，交流讨论，写笔记发布在掘金。再在掘金这篇文章下评论放上提交笔记的链接。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

本文为稀土掘金技术社区首发签约文章，14天内禁止转载，14天后未获授权禁止转载，侵权必究！

背景

写在前面

本文是Three.js 进阶之旅系列专栏的首篇文章，本专栏的主要内容具体规划如下：前两篇将简要介绍 Three.js 开发环境搭建以及Three.js 的一些基础概念和必备知识，如果读者已经有一定的 Three.js 3D项目开发基础，可以直接跳过这两章内容。后续文章会通过一个个趣味的 3D 页面实例，逐步讲解 Three.js 相关性能优化、着色器、后期渲染、物理特性等应用中知识，期间也会穿插介绍一些 3D 建模、压缩工具和技巧。本专栏适用于有一定 JavaScript 和 CSS 编程基础的同学，相信阅读完此专栏，一定会对 Three.js 有进一步的理解。

一些约定

为了规范化文章写作，在本系列文章写作制定了一些约定，大家可以根据以下符号以及文字样式格式迅速找到自己感兴趣的内容，后续文章都将沿用此格式。

文章目录结构：

• 摘要：本文包含重要内容的概括性描述。
• 效果：根据本文内容构建的页面效果。
• 实现：具体实现步骤及涉及到的知识点。
• 总结：本文涉及的知识点列表清单。
• 附录：本文的外部引用及其一些附加内容。

文章内容标注：

• 强调内容：粗体文本
• 知识点：💡 知识点
• 注意点：📌 注意

正文

Three.js 简介

随着 HTML5 标准的颁布，以及主流浏览器的功能日益强大，直接在浏览器中展示三维图像和动画已经变得越来越容易。WebGL 技术为在浏览器中创建丰富的三维图形提供了丰富且强大的接口，它们不仅可以创建二维图形和应用，还可以充分利用 GPU，创建漂亮的、高性能的三维应用。

但是直接使用 WebGL 编程非常复杂，需要了解 WebGL 的内部细节，学习复杂的着色器语法和足够多的数学和图形学方面的专业知识才能学好 WebGL。

Three.js 就是一款基于原生 WebGL 封装运行在浏览器中的 3D 引擎，可以用它创建各种三维场景，包括了摄影机、光影、材质等各种对象。使用 Three.js 不必学习 WebGL 的详细细节，就能轻松创建出漂亮的三维图形。

开发环境

Three.js 支持在 <script>标签从直接从本地文件目录或 CDN 及静态主机引入，也支持使用 `NPM 下载安装并在项目页面导入。

1

html复制代码<script src="https://cdn.skypack.dev/three@<version>"></script>

要安装 three 的 npm 模块，需要在项目文件夹里打开终端窗口，并运行以下命令，包将会被下载并安装，然后就可以将它导入我们的代码了。

1

cmd复制代码npm install --save three

引入方式1：导入整个 Three.js 核心库

1
2

js复制代码import * as THREE from 'three';
const scene = new THREE.Scene();

引入方式2：按需导入你所需要的内容

1
2

js复制代码import { Scene } from 'three';
const scene = new Scene();

本文及后续文章都将使用 NPM 安装导入的形式，并使用 Webpack 进行本地热加载更新和打包。本专栏系列项目已经配置好开发环境，大家只需克隆仓库安装即可，不必从头开始配置。项目托管在 Github 仓库【threejs-odessey】，后续所有专栏项目目录都将在这个仓库中更新。

🔗 代码仓库地址：git@github.com:dragonir/threejs-ode…

先来看看仓库目录的基本结构

其中 bundler 目录是 Webpack 的配置文件目录；dist 目录是打包之后的文件，src 就是主要开发目录，后续所有的开发工作都将在此文件夹完成，index.html 是主页面，页面逻辑相关代码位于 script.js、style.css 是全局样式表；static 用于存放一些静态资源，如开发所需的图面，模型等。后续随着页面功能的扩展以及对性能优化的考虑，会对目录进行按模块拆分，当前目录只适应于交互比较简单的单页面应用。

运行环境

本专栏目录下的所有示例都将使用原生 JavaScript 开发，因此可以很容易移植到其他如React、Vue、Anaular、jQuery 等项目中，大家克隆代码后直接在项目中运行 npm install 及 npm run dev 即可，页面会自动在默认浏览器中打开，对代码内容修改也会实时反映到浏览器。

部署环境

项目开发完成后，为了给他人展示页面，我们可以运行 npm run build，然后将 dist 文件夹中的打包文件进行部署，可以选择部署在 Github Page、Vercel、Codepen、码上掘金 等免费静态页面服务上，也可以部署到自己的服务器上。（Vercel是一个很好用的前端可持续继承部署服务，可以关联 Github，静态页面可以免费部署并能生成预览链接）。

📌 由于项目采用纯原生 JavaScript 开发，因此可以直接移移植到码上掘金部署预览。当然，直接使用码上掘金开发也是不错的。

入门示例

Three.js 项目整体开发流程可以按照以下步骤进行，其中有些步骤可以并行进行。后续本专栏所有项目也都将按照这个流程进行开发。

• 容器构建：添加需要渲染 3D 内容的容器和基本页面结构。
• 引入资源：导入Three.js、以及开发页面功能所需要的其他库、静态资源等。
• 场景初始化：定义一些全局变量如渲染尺寸、容器等；初始化渲染器；初始化场景；处理页面缩放事件监听处理等。
• 逻辑开发：按需求开发业务功能，并将其添加到场景中。
• 动画更新：更新渲染器和相机，并根据业务需求，更新其他网格模型的动画。
• 性能优化：离开页面时释放 GPU 资源、清除定时器和动画等。
• 修饰优化：使用 CSS、图片等元素装饰界面，提升页面视觉效果。

容器构建

配置完成开发环境，现在马上可以尝试开发自己的第一个 Three.js 3D 页面。首先 index.html 中构建基本如下的页面结构，如不需要显示额外的元素，则只需要在 body 中添加一个 canvas 元素即可。

1
2
3
4
5
6
7
8
9
10
11

html复制代码<!DOCTYPE html>
<html lang="zh-cn">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>01 - Introduction</title>
</head>
<body>
  <canvas class="webgl"></canvas>
</body>
</html>

引入资源

在顶部引 样式表 和 Three.js，Three.js可以像示例中一样全量引入，也可以这样 import { Scene } from 'three' 这样按需引入以减少文件体积，提高加载速率。

1
2

js复制代码import './style.css';
import * as THREE from 'three';

场景初始化

定义好渲染尺寸的常量，我们需要覆盖满整个窗口，所以宽高的取值是 window.innerWidth 和 window.innerHeight。如果需要渲染到具体 DOM 中，那么宽高就取 DOM 的宽高。然后初始化渲染器、场景和相机。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

js复制代码// 定义渲染尺寸
const sizes = {
  width: window.innerWidth,
  height: window.innerHeight
}

// 初始化渲染器
const canvas = document.querySelector('canvas.webgl');
const renderer = new THREE.WebGLRenderer({ canvas: canvas });
renderer.setSize(sizes.width, sizes.height);
renderer.setPixelRatio(Math.min(window.devicePixelRatio, 2));

// 初始化场景
const scene = new THREE.Scene();

// 初始化相机
const camera = new THREE.PerspectiveCamera(75, sizes.width / sizes.height, 0.1, 100);
camera.position.z = 3;
scene.add(camera);

知识点 💡 渲染器 WebGLRenderer

WebGLRenderer 用 WebGL 渲染出场景。通过 new THREE.WebGLRenderer 初始化渲染器，并将 canvas 容器作为参数传给它。通过调用 setSize 方法设置渲染器的尺寸；调用 setPixelRatio 设置 canvas 的像素比为当前设备的屏幕像素比，避免高分屏下出现模糊情况。

知识点 💡 场景 Scene

Scene 是场景对象，所有的网格对象、灯光、动画等都需要放在场景中，使用 new THREE.Scene 初始化场景，下面是场景的一些常用属性和方法。

• fog：设置场景的雾化效果,可以渲染出一层雾气，隐层远处的的物体。
• overrideMaterial：强制场景中所有物体使用相同材质。
• autoUpdate：设置是否自动更新。
• background：设置场景背景，默认为黑色。
• children：所有对象的列表。
• add()：向场景中添加对象。
• remove()：从场景中移除对象。
• getChildByName()：根据名字直接返回这个对象。
• traverse()：传入一个回调函数访问所有的对象。

知识点 💡 透视相机 PerspectiveCamera

为了在场景中显示物体，就必须给场景添加相机，相机类型可以分为正交相机和透视相机，本例中使用的是透视相机 PerspectiveCamera，可以像下面这样使用透视相机。

构造函数：

1

js复制代码PerspectiveCamera(fov, aspect, near, far)

• fov：表示视场，就是能够看到的角度范围，人的眼睛大约能够看到 180度 的视场，视角大小设置要根据具体应用，一般游戏会设置 60~90 度，默认值 45。
• aspect：表示渲染窗口的长宽比，如果一个网页上只有一个全屏的 canvas 画布且画布上只有一个窗口，那么 aspect 的值就是网页窗口客户区的宽高比 window.innerWidth/window.innerHeight。
• near：属性表示的是从距离相机多远的位置开始渲染，一般情况会设置一个很小的值。 默认值 0.1。
• far：属性表示的是距离相机多远的位置截止渲染，如果设置的值偏小，会有部分场景看不到，默认值 1000。

页面缩放适配

为了防止画布渲染内容在浏览器尺寸发生变化时产生变形和移位，可以对 resize 事件进行监听，当页面发生变化时，同时更新渲染器的尺寸和相机视角比例，并调用 .updateProjectionMatrix() 手动更新相机对象的投影矩阵属性。

1
2
3
4
5
6
7
8
9
10
11

js复制代码// 页面缩放事件监听
window.addEventListener('resize', () => {
  sizes.width = window.innerWidth;
  sizes.height = window.innerHeight;
  // 更新渲染
  renderer.setSize(sizes.width, sizes.height);
  renderer.setPixelRatio(Math.min(window.devicePixelRatio, 2))
  // 更新相机
  camera.aspect = sizes.width / sizes.height;
  camera.updateProjectionMatrix();
});

逻辑开发

要创建可加载显示在场景中的内置三维模型，需要添加网格 Mesh，并为它创建几何体 Geometry 和 材质 Material。本示例中添加了一个 Three.js 内置的立方体网格模型。

1
2
3
4

js复制代码const geometry = new THREE.BoxGeometry(1, 1, 1);
const material = new THREE.MeshBasicMaterial({ color: 0x03c03c });
const mesh = new THREE.Mesh(geometry, material);
scene.add(mesh);

知识点 💡 立方体 BoxGeometry

BoxGeometry 是四边形的原始几何类，来创建立方体或者不规则四边形。

构造函数：

1

js复制代码BoxGeometry(width : Float, height : Float, depth : Float, widthSegments : Integer, heightSegments : Integer, depthSegments : Integer)

• width：X轴 的宽度，默认为 1。
• height：Y轴 的高度，默认为 1。
• depth：Z轴 的深度，默认为 1。
• widthSegments：可选，宽度的分段数，默认是 1。
• heightSegments：可选，高度的分段数，默认是 1。
• depthSegments：可选，深度的分段数，默认是 1。

知识点 💡 基础网格材质 MeshBasicMaterial

基础网格材质是一种一个以简单着色方式来绘制几何体的材质，它不受光照的影响。

构造函数：

1

js复制代码MeshBasicMaterial(parameters: Object)

• parameters：可选，用于定义材质外观的对象，具有一个或多个属性如 color、map 等。

动画更新

完成上面的内容，如果你在浏览器中直接运行，会发现页面不会加载任何东西，因为还没有进行真正的渲染。为此，我们需要调用 requestAnimationFrame 在页面重回动画中更新渲染内容。在这里创建了一个 tick 动画方法，它的功能是使渲染器可以在每次屏幕刷新时对场景进行绘制的循环，在大多数屏幕上，requestAnimationFrame 刷新率一般为 60次/秒。

1
2
3
4
5
6
7
8
9
10
11

js复制代码// 动画
const tick = () => {
  // 更新渲染器
  renderer.render(scene, camera);
  // 给网格模型添加一个转动动画
  mesh && (mesh.rotation.y += .02);
  mesh && (mesh.rotation.x += .02);
  // 页面重绘时调用自身
  window.requestAnimationFrame(tick);
}
tick();

运行效果

到此，入门示例全部开发完毕了，在浏览器中打开可以看到如下的 3D 界面。

提示

因为 Scene 默认场景背景是黑色的，而浏览器在常规下默认的背景色是白色的，在 Mac 上用鼠标拖拽屏幕时可能会出现露出底部白色的问题，我们可以通过设置以下样式解决此问题。

1
2
3
4
5
6
7
8
9
10
11
12
13

css复制代码* {
  margin: 0;
  padding: 0;
}
html, body {
  overflow: hidden;
}
.webgl {
  position: fixed;
  top: 0;
  left: 0;
  outline: none;
}

🔗 源码仓库地址：github.com/dragonir/th…

总结

本文中主要包含的知识点包括：

• Three.js 的安装和引用
• Three.js 初始化项目搭建
• 开发基于 Three.js 项目的基本步骤
• 渲染器 WebGLRenderer
• 场景 Scene
• 透视相机 PerspectiveCamera
• 页面缩放适配
• 立方体 BoxGeometry
• 基础网格材质 MeshBasicMaterial
• requestAnimationFrame 动画更新

想了解其他前端知识或其他未在本文中详细描述的Web 3D开发技术相关知识，可阅读我往期的文章。如果有疑问可以在评论中留言，如果觉得文章对你有帮助，不要忘了一键三连哦 👍。

附录

• 【Three.js 进阶之旅】系列专栏访问 👈
• 更多往期【3D】专栏访问 👈
• [1]. 🌴 Three.js 打造缤纷夏日3D梦中情岛
• [2]. 🔥 Three.js 实现炫酷的赛博朋克风格3D数字地球大屏
• [3]. 🐼 Three.js 实现2022冬奥主题3D趣味页面，含冰墩墩
• [4]. 🏆 掘金1000粉！使用Three.js实现一个创意纪念页面
• ...

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。

学习数据结构与算法的关键在于掌握问题背后的算法思维框架，你的思考越抽象，它能覆盖的问题域就越广，理解难度也更复杂。在这个专栏里，小彭将基于 Java / Kotlin 语言，为你分享常见的数据结构与算法问题，及其解题框架思路。

本文是数据结构与算法系列的第 12 篇文章，完整文章目录请移步到文章末尾~

前言

大家好，我是小彭。

在上一篇文章中，我们介绍了单调栈这种特殊的栈结构，单调栈是一种非常适合处理 “下一个更大元素问题” 的数据结构。今天，分享到单调栈的孪生兄弟 —— 单调队列（Monotonic Queue）。类似地，单调队列也是在队列的基础上增加了单调的性质（单调递增或单调递减）。那么单调队列是用来解决什么问题的呢？

思维导图：

1. 单调队列的典型问题

单调队列是一种用来高效地解决 “滑动窗口最大值” 问题的数据结构。

举个例子，给定一个整数数组，要求输出数组中大小为 K 的窗口中的最大值，这就是窗口最大值问题。而如果窗口从最左侧逐渐滑动到数组的最右端，要求输出每次移动后的窗口最大值，这就是滑动窗口问题。这个问题同时也是 LeetCode 上的一道典型例题：LeetCode · 239. 滑动窗口最大值

LeetCode 例题

这个问题的暴力解法很容易想到：就是每次移动后遍历整个滑动窗口找到最大值，单次遍历的时间复杂度是 O(k)O(k)O(k)，整体的时间复杂度是 O(n⋅k)O(n·k)O(n⋅k)，空间复杂度是 O(1)O(1)O(1)。当然，暴力解法里的重复比较运算也是很明显的，我们每次仅仅往窗口里增加一个元素，都需要与窗口中所有元素对比找到最大值。

那么，有没有更高效的算法呢？

滑动窗口最大值问题

或许，我们可以使用一个变量来记录上一个窗口中的最大值，每增加一个新元素，只需要与这个 “最大值” 比较即可。

然而，窗口大小是固定的，每加入一个新元素后，也要剔除一个元素。如果剔除的元素正好是变量记录的最大值，那说明这个值已经失效。我们还是需要花费 O(k)O(k)O(k) 时间重新找出最大值。那还有更快的方法寻找最大值吗？

2. 解题思路

我们先用 “空间换时间” 的通用思路梳理一下：

在暴力解法中，我们每移动一次窗口都需要遍历整个窗口中的所有元素找出 “滑动窗口的最大值”。现在我们不这么做，我们把滑动窗口中的所有元素缓存到某种数据容器中，每次窗口滑动后也向容器增加一个新的元素，而容器的最大值就自然是滑动窗口的最大值。

现在，我们的问题已经发生转变，问题变成了：“如何寻找数据容器中的最大值”。 另外，根据题目条件限制，这个容器是带有约束的：因为窗口大小是固定的，所以每加入一个新元素后，必然也要剔除一个元素。 我们的数据容器也要满足这个约束。 现在，我们把注意力集中在这个容器上，思考一下用什么数据结构、用什么算法可以更高效地解决问题。由于这个容器是我们额外增加的，所以我们有足够的操作空间。

先说结论：

• 方法 1 - 暴力： 遍历整个数据容器中所有元素，单次操作的时间复杂度是 O(k)O(k)O(k)，整体时间复杂度是 O(n⋅k)O(n·k)O(n⋅k)；
• 方法 2 - 二叉堆： 不需要遍历整个数据容器，可以用大顶堆维护容器的最大值，单次操作的时间复杂度是 O(lgk)O(lgk)O(lgk)，整体时间复杂度是 O(n⋅lgk)O(n·lgk)O(n⋅lgk)；
• 方法 3 - 双端队列： 我们发现二叉堆中很多中间元素是冗余的，拉低了效率。我们可以在每处理一个元素时，可以先观察容器中刚刚加入的元素，如果刚刚加入的元素小于当前元素，则直接将其丢弃（后进先出逻辑）。最先加入容器的元素，如果超出了滑动窗口的范围，也直接将其丢弃（先进先出逻辑）。所以这个容器数据结构要用双端队列实现。因为每个元素最多只会入队和出队一次，所以整体的计算规模还是与数据规模成正比的，整体时间复杂度是 O(n)O(n)O(n)。

下面，我们先从优先队列说起。

3. 优先队列解法

寻找最值的问题第一反应要想到二叉堆。

我们可以维护一个大顶堆，初始时先把第一个滑动窗口中的前 k−1k - 1k−1 个元素放入大顶堆。滑动窗口每移动一步，就把一个新的元素放入大顶堆。大顶堆会自动进行堆排序，堆顶的元素就是整个堆中 kkk 个元素的最值。然而，这个最大值可能是失效的（不在滑动窗口的范围内），我们要怎么处理这个约束呢？

我们可以用一个小技巧：将元素的下标放入队列中，用 nums[index] 比较元素大小，用 index 判断元素有效性。 此时，每次取堆顶元素时，如果发现该元素的下标超出了窗口范围，就直接丢弃。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

kotlin复制代码class Solution {
    fun maxSlidingWindow(nums: IntArray, k: Int): IntArray {
        // 结果数组
        val result = IntArray(nums.size - k + 1) {-1}
        // 大顶堆
        val heap = PriorityQueue<Int> { first, second ->
            nums[second] - nums[first]
        }
        for (index in nums.indices) {
            if (index < k - 1) {
                heap.offer(index)
                continue
            }
            heap.offer(index)
            // while：丢弃堆顶超出滑动窗口范围的失效元素
            while (!heap.isEmpty() && heap.peek() < index - k + 1) {
                // 丢弃
                heap.poll()
            }
            // 堆顶元素就是最大值
            result[index - k + 1] = nums[heap.peek()]
        }
        return result
    }
}

我们来分析优先队列解法的复杂度：

• 时间复杂度： 最坏情况下（递增序列），所有元素都被添加到优先队列里，优先队列的单次操作时间复杂度是 O(lgn)O(lgn)O(lgn)，所以整体时间复杂度是 O(n⋅lgn)O(n·lgn)O(n⋅lgn)；
• 空间复杂度： 使用了额外的优先级队列，所以整体的时间复杂度是 O(n)O(n)O(n)。

优先队列解法的时间复杂度从 O(n⋅k)O(n·k)O(n⋅k) 变成 O(n⋅lgn)O(n·lgn)O(n⋅lgn)，这个效果很难让人满意，有更好的办法吗？

我们继续分析发现，由于滑动窗口是从左往右移动的，所以当一个元素 nums[i]nums[i]nums[i] 的后面出现一个更大的元素 nums[j]nums[j]nums[j]，那么 nums[i]nums[i]nums[i] 就永远不可能是滑动窗口的最大值了，我们可以永久地将它剔除掉。然而，在优先队列中，失去价值的 nums[i]nums[i]nums[i] 会一直存储在队列中，从而拉低了优先队列的效率。

4. 单调队列解法

我们可以维护一个数据容器，第一个元素先放到容器中，后续每处理一个元素，先观察容器中刚刚加入的元素，如果刚刚加入的元素小于当前元素，则直接将其丢弃（因为新增加的元素排在后面，会更晚地离开滑动窗口，所以中间的小元素永远没有资格了），避免拉低效率。

继续分析我们还发现：

• 这个数据容器中后进入的元素需要先弹出与当前元素对比，符合 “后进先出” 逻辑，所以这个数据结构要用栈；
• 这个数据容器中先进入的元素需要先弹出丢弃（离开滑动窗口），符合 “先进先出” 逻辑，所以这个数据结构要用队列；

因此，这个数据结构同时具备栈和队列的特点，是需要同时在两端操作的双端队列。这个问题也可以形象化地思考：把数字想象为有 “重量” 的的杠铃片，滑动窗口每移动一次后，新增加的大杠铃片会把中间小的杠铃片压扁，后续不再考虑它们。

形象化思考

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

kotlin复制代码class Solution {
    fun maxSlidingWindow(nums: IntArray, k: Int): IntArray {
        // 结果数组
        val result = IntArray(nums.size - k + 1) { -1 }
        // 单调队列（基于双端队列）
        val queue = LinkedList<Int>()
        for (index in nums.indices) {
            // while：队尾元素比当前元素小，说明队尾元素不再可能是最大值，后续不再考虑它
            while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[index]) {
                // 抛弃队尾元素
                queue.pollLast()
            }
            queue.offerLast(index)
            if (index < k - 1) {
                continue
            }
            // if：移除队头超出滑动窗口范围的元素
            if (!queue.isEmpty() && queue.peekFirst() < index - k + 1) {
                queue.pollFirst()
            }
            // 从队头取目标元素
            result[index - k + 1] = nums[queue.peekFirst()]
        }
        return result
    }
}

单调队列与单调栈的思路是非常类似的，单调栈在每次遍历中，会将栈顶 “被压扁的小杠铃片” 弹出栈，而单调队列在每次遍历中，会将队尾中 “被压扁的小杠铃片” 弹出队。 单调栈在栈顶过滤无效元素，在栈顶获取目标元素，单调队列在队尾过滤无效元素，在队头获取目标元素。

理解了单调队列的解题模板后，我们来分析它的复杂度：

• 时间复杂度： 虽然代码中有嵌套循环，但它的时间复杂度并不是 O(n2)O(n^2)O(n2)，而是 O(n)O(n)O(n)。因为每个元素最多只会入栈和出栈一次，所以整体的计算规模还是与数据规模成正比的，整体时间复杂度是 O(n)O(n)O(n)；
• 空间复杂度： 最坏情况下（递增序列），所有元素被添加到队列中，所以空间复杂度是 O(n)O(n)O(n)。

5. 单调栈、单调队列、优先队列对比

5.1 单调栈与单调队列的选择

单调队列和单调栈在很大程度上是类似的，它们均是在原有数据结构的基础上增加的单调的性质。那么，什么时候使用单调栈，什么时候使用单调队列呢？ 主要看你的算法中元素被排除的顺序，如果先进入集合的元素先排除，那么使用栈（LIFO）；如果先进入集合的元素后排除，那么使用队列（FIFO）。 在例题中，甚至出现了同时结合栈和队列的情况。

上一篇文章里我们讨论过单调栈，单调栈是一种非常适合解决 ”下一个更大元素“ 的数据结构。在文章最后我也指出，单调栈的关键是 “单调性”，而不是 “栈”。我们学习单调栈和单端队列，应该当作学习单调性的思想在栈或者队列上的应用。

我们已经不是第一次讨论 “单调性” 了，老读者应该有印象，在讨论二分查找时，我们曾经指出 “单调性是二分查找的必要条件”。举个例子，对于一个单调递增序列，当中位数小于目标数时，那我们可以确定：左半区间一定不是解，右半区间可能有解，问题规模直接缩小一半。最终整个二分查找算法的时间复杂度从暴力查找 O(n)O(n)O(n)，降低到 O(lgn)O(lgn)O(lgn)。反之，如果数据并不是单调的，那么跟中位数比较就没有意义。

5.2 优先队列与单调队列对比

优先队列也叫小顶堆或大顶堆，每从堆顶取一个数据，底层的二叉堆会自动进行堆排序，保持堆顶元素是整个堆的最值。所以，虽然整个堆不是单调的，但堆顶是动态单调的。优先队列虽然也叫队列，但它并不能维护元素的位置关系，出队顺序和入队顺序无关。

6. 总结

到这里，单调队列和单调栈的内容都讲完了。和单调栈一样，除了典型例题之外，大部分题目会将 “滑动窗口最大值素” 的语义隐藏在题目细节中，需要找出题目的抽象模型或转换思路才能找到，这是难的地方。

还是那句话，学习单调队列和单调栈，应该当作学习单调性的思想在这两种数据结构上的应用。你觉得呢？

更多同类型题目：

版权声明

本文为稀土掘金技术社区首发签约文章，14天内禁止转载，14天后未获授权禁止转载，侵权必究！

参考资料

• LeetCode 专题 · 单调队列 —— LeetCode 出品
• LeetCode 题解 · 239. 滑动窗口最大值 —— LeetCode 出品
• LeetCode 题解 · 239. 单调队列解题详解 —— labuladong 著

推荐阅读

数据结构与算法系列完整目录如下（2023/07/11 更新）：

• #1 链表问题总结
• #2 链表相交 & 成环问题总结
• #3 计算器与逆波兰表达式总结
• #4 高楼丢鸡蛋问题总结
• #5 为什么你学不会递归？谈谈我的经验
• #6 回溯算法解题框架总结
• #7 下次面试遇到二分查找，别再写错了
• #8 什么是二叉树？
• #9 什么是二叉堆 & Top K 问题
• #10 使用前缀和数组解决 “区间和查询” 问题
• #11 面试遇到线段树，已经这么卷了吗？
• #12 使用单调队列解决 “滑动窗口最大值” 问题
• #13 使用单调栈解决 “下一个更大元素” 问题
• #14 使用并查集解决 “朋友圈” 问题
• #15 如何实现一个优秀的 HashTable 散列表
• #16 简答一波 HashMap 常见面试题
• #17 二叉树高频题型汇总
• #18 下跳棋，极富想象力的同向双指针模拟

Java & Android 集合框架系列文章: 跳转阅读

LeetCode 上分之旅系列文章：跳转阅读

⭐️ 永远相信美好的事情即将发生，欢迎加入小彭的 Android 交流社群~

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。

学习数据结构与算法的关键在于掌握问题背后的算法思维框架，你的思考越抽象，它能覆盖的问题域就越广，理解难度也更复杂。在这个专栏里，小彭将基于 Java / Kotlin 语言，为你分享常见的数据结构与算法问题，及其解题框架思路。

本文是数据结构与算法系列的第 13 篇文章，完整文章目录请移步到文章末尾~

前言

大家好，我是小彭。

今天分享到一种栈的衍生数据结构 —— 单调栈（Monotonic Stack）。栈（Stack）是一种满足后进先出（LIFO）逻辑的数据结构，而单调栈实际上就是在栈的基础上增加单调的性质（单调递增或单调递减）。那么，单调栈是用来解决什么问题的呢？

思维导图：

1. 单调栈的典型问题

单调栈是一种特别适合解决 “下一个更大元素” 问题的数据结构。

举个例子，给定一个整数数组，要求输出数组中元素 iii 后面下一个比它更大的元素，这就是下一个更大元素问题。这个问题也可以形象化地思考：站在墙上向后看，问视线范围内所能看到的下一个更高的墙。例如，站在墙 [3] 上看，下一个更高的墙就是墙 [4] 。

形象化思考

这个问题的暴力解法很容易想到：就是遍历元素 iii 后面的所有元素，直到找到下一个比 iii 更大的元素为止，时间复杂度是 O(n)O(n)O(n)，空间复杂度是 O(1)O(1)O(1)。单次查询确实没有优化空间了，那多次查询呢？如果要求输出数组中每个元素的下一个更大元素，那么暴力解法需要的时间复杂度是 O(n2)O(n^2)O(n2) 。有没有更高效的算法呢？

2. 解题思路

我们先转变一下思路：

在暴力解法中，我们每处理一个元素就要去求它的 “下一个更大元素”。现在我们不这么做，我们每处理一个元素时，由于不清楚它的解，所以先将它缓存到某种数据容器中。后续如果能确定它的解，再将其从容器中取出来。 这个思路可以作为 “以空间换时间” 优化时间复杂度的通用思路。

回到这个例子上：

• 在处理元素 [3] 时，由于不清楚它的解，只能先将 [3] 放到容器中，继续处理下一个元素；
• 在处理元素 [1] 时，我们发现它比容器中所有元素都小，只能先将它放到容器中，继续处理下一个元素；
• 在处理元素 [2] 时，我们观察容器中的 [1] 比当前元素小，说明当前元素就是 [1] 的解。此时我们可以把 [1] 弹出，记录结果。再将 [2] 放到容器中，继续处理下一个元素；
• 在处理元素 [1] 时，我们发现它比容器中所有元素都小，只能先将它放到容器中，继续处理下一个元素；
• 在处理元素 [4] 时，我们观察容器中的 [3] [2] [1] 都比当前元素小，说明当前元素就是它们的解。此时我们可以把它们弹出，记录结果。再将 [4] 放到容器中，继续处理下一个元素；
• 在处理元素 [1] 时，我们发现它比容器中所有元素都小，只能先将它放到容器中，继续处理下一个元素；
• 遍历结束，所有被弹出过的元素都是有解的，保留在容器中的元素都是无解的。

分析到这里，我们发现问题已经发生转变，问题变成了：“如何寻找在数据容器中小于当前元素的数”。 现在，我们把注意力集中在这个容器上，思考一下用什么数据结构、用什么算法可以更高效地解决问题。由于这个容器是我们额外增加的，所以我们有足够的操作空间。

先说结论：

• 方法 1 - 暴力： 遍历整个数据容器中所有元素，最坏情况（递减序列）下所有数据都进入容器中，单次操作的时间复杂度是 O(N)O(N)O(N)，整体时间复杂度是 O(N2)O(N^2)O(N2)；
• 方法 2 - 二叉堆： 不需要遍历整个容器，只需要对比容器的最小值，直到容器的最小值都大于当前元素。最坏情况（递减序列）下所有数据都进入堆中，单次操作的时间复杂度是 O(lgN)O(lgN)O(lgN)，整体时间复杂度是 O(N⋅lgN)O(N·lgN)O(N⋅lgN)；
• 方法 3 - 单调栈： 我们发现元素进入数据容器的顺序正好是有序的，且后进入容器的元素会先弹出做对比，符合 “后进先出” 逻辑，所以这个容器数据结构用栈就可以实现。因为每个元素最多只会入栈和出栈一次，所以整体的计算规模还是与数据规模成正比的，整体时间复杂度是 O(n)O(n)O(n)。

下面，我们先从优先队列说起。

3. 优先队列解法

寻找最值的问题第一反应要想到二叉堆。

我们可以维护一个小顶堆，每处理一个元素时，先观察堆顶的元素：

• 如果堆顶元素小于当前元素，则说明已经确定了堆顶元素的解，我们将其弹出并记录结果；
• 如果堆顶元素不小于当前元素，则说明小顶堆内所有元素都是不小于当前元素的，停止观察。

观察结束后，将当前元素加入小顶堆，堆会自动进行堆排序，堆顶就是整个容器的最小值。此时，继续在后续元素上重复这个过程。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

kotlin复制代码fun nextGreaterElements(nums: IntArray): IntArray {
    // 结果数组 
    val result = IntArray(nums.size) { -1 }
    // 小顶堆
    val heap = PriorityQueue<Int> { first, second ->
        nums[first] - nums[second]
    }
    // 从前往后查询
    for (index in 0 until nums.size) {
        // while：当前元素比堆顶元素大，说明找到下一个更大元素
        while (!heap.isEmpty() && nums[index] > nums[heap.peek()]) {
            result[heap.poll()] = nums[index]
        }
        // 当前元素入堆
        heap.offer(index)
    }
    return result
}

我们来分析优先队列解法的复杂度：

• 时间复杂度： 最坏情况下（递减序列），所有元素都被添加到优先队列里，优先队列的单次操作时间复杂度是 O(lgN)O(lgN)O(lgN)，所以整体时间复杂度是 O(N⋅lgN)O(N·lgN)O(N⋅lgN)；
• 空间复杂度： 使用了额外的优先队列，所以整体的空间复杂度是 O(N)O(N)O(N)。

优先队列解法的时间复杂度从 O(N2)O(N^2)O(N2) 优化到 O(N⋅lgN)O(N·lgN)O(N⋅lgN)，还不错，那还有优化空间吗？

4. 单调栈解法

我们继续分析发现，元素进入数据容器的顺序正好是逆序的，最后加入容器的元素正好就是容器的最小值。此时，我们不需要用二叉堆来寻找最小值，只需要获取最后一个进入容器的元素就能轻松获得最小值。这符合 “后进先出” 逻辑，所以这个容器数据结构用栈就可以实现。

这个问题也可以形象化地思考：把数字想象成有 “重量” 的杠铃片，每增加一个杠铃片，会把中间小的杠铃片压扁，当前的大杠铃片就是这些被压扁杠铃片的 “下一个更大元素”。

形象化思考

解题模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

kotlin复制代码// 从前往后遍历
fun nextGreaterElements(nums: IntArray): IntArray {
    // 结果数组 
    val result = IntArray(nums.size) { -1 }
    // 单调栈
    val stack = ArrayDeque<Int>()
    // 从前往后遍历
    for (index in 0 until nums.size) {
        // while：当前元素比栈顶元素大，说明找到下一个更大元素
        while (!stack.isEmpty() && nums[index] > nums[stack.peek()]) {
            result[stack.pop()] = nums[index]
        }
        // 当前元素入队
        stack.push(index)
    }
    return result
}

理解了单点栈的解题模板后，我们来分析它的复杂度：

• 时间复杂度： 虽然代码中有嵌套循环，但它的时间复杂度并不是 O(N2)O(N^2)O(N2)，而是 O(N)O(N)O(N)。因为每个元素最多只会入栈和出栈一次，所以整体的计算规模还是与数据规模成正比的，整体时间复杂度是 O(N)O(N)O(N)；
• 空间复杂度： 最坏情况下（递减序列）所有元素被添加到栈中，所以空间复杂度是 O(N)O(N)O(N)。

这道题也可以用从后往前遍历的写法，也是参考资料中提到的解法。 但是，我觉得正向思维更容易理解，也更符合人脑的思考方式，所以还是比较推荐小彭的模板（王婆卖瓜）。

解题模板（从后往前遍历）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

kotlin复制代码// 从后往前遍历
fun nextGreaterElement(nums: IntArray): IntArray {
    // 结果数组
    val result = IntArray(nums.size) { -1 }
    // 单调栈
    val stack = ArrayDeque<Int>()
    // 从后往前查询
    for (index in nums.size - 1 downTo 0) {
        // while：栈顶元素比当前元素小，说明栈顶元素不再是下一个更大元素，后续不再考虑它
        while (!stack.isEmpty() && stack.peek() <= nums[index]) {
            stack.pop()
        }
        // 输出到结果数组
        result[index] = stack.peek() ?: -1
        // 当前元素入队
        stack.push(nums[index])
    }
    return result
}

5. 典型例题 · 下一个更大元素 I

理解以上概念后，就已经具备解决单调栈常见问题的必要知识了。我们来看一道 LeetCode 上的典型例题：LeetCode 496.

LeetCode 例题

第一节的示例是求 “在当前数组中寻找下一个更大元素” ，而这道题里是求 “数组 1 元素在数组 2 中相同元素的下一个更大元素” ，还是同一个问题吗？其实啊，这是题目抛出的烟雾弹。注意看细节信息：

• 两个没有重复元素的数组 nums1和 nums2 ；
• nums1 是 nums2 的子集。

那么，我们完全可以先计算出 nums2 中每个元素的下一个更大元素，并把结果记录到一个散列表中，再让 nums1 中的每个元素去散列表查询结果即可。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

kotlin复制代码class Solution {
    fun nextGreaterElement(nums1: IntArray, nums2: IntArray): IntArray {
        // 临时记录
        val map = HashMap<Int, Int>()
        // 单调栈
        val stack = ArrayDeque<Int>()
        // 从前往后查询
        for (index in 0 until nums2.size) {
            // while：当前元素比栈顶元素大，说明找到下一个更大元素
            while (!stack.isEmpty() && nums2[index] > stack.peek()) {
                // 输出到临时记录中
                map[stack.pop()] = nums2[index]
            }
            // 当前元素入队
            stack.push(nums2[index])
        }

        return IntArray(nums1.size) {
            map[nums1[it]] ?: -1
        }
    }
}

6. 典型例题 · 下一个更大元素 II（环形数组）

第一节的示例还有一道变型题，对应于 LeetCode 上的另一道典型题目：503. 下一个更大元素 II

LeetCode 例题

两道题的核心考点都是 “下一个更大元素”，区别只在于把 “普通数组” 变为 “环形数组 / 循环数组”，当元素遍历到数组末位后依然找不到目标元素，则会循环到数组首位继续寻找。这样的话，除了所有数据中最大的元素，其它每个元素都必然存在下一个更大元素。

其实，计算机中并不存在物理上的循环数组，在遇到类似的问题时都可以用假数据长度和取余的思路处理。如果你是前端工程师，那么你应该有印象：我们在实现无限循环轮播的控件时，有一个小技巧就是给控件 设置一个非常大的数据长度 ，长到永远不可能轮播结束，例如 Integer.MAX_VALUE。每次轮播后索引会加一，但在取数据时会对数据长度取余，这样就实现了循环轮播了。

无限轮播伪代码

1
2
3
4
5
6
7
8
9
10

kotlin复制代码class LooperView {

    private val data = listOf("1", "2", "3")		

    // 假数据长度
    fun getSize() = Integer.MAX_VALUE

    // 使用取余转化为 data 上的下标
    fun getItem(index : Int) = data[index % data.size]
}

回到这道题，我们的思路也更清晰了。我们不需要无限查询，所以自然不需要设置 Integer.MAX_VALUE 这么大的假数据，只需要 设置 2 倍的数据长度 ，就能实现循环查询（3 倍、4倍也可以，但没必要），例如：

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

kotlin复制代码class Solution {
    fun nextGreaterElements(nums: IntArray): IntArray {
        // 结果数组 
        val result = IntArray(nums.size) { -1 }
        // 单调栈
        val stack = ArrayDeque<Int>()
        // 数组长度
        val size = nums.size
        // 从前往后遍历
        for (index in 0 until nums.size * 2) {
            // while：当前元素比栈顶元素大，说明找到下一个更大元素
            while (!stack.isEmpty() && nums[index % size] > nums[stack.peek() % size]) {
                result[stack.pop() % size] = nums[index % size]
            }
            // 当前元素入队
            stack.push(index)
        }
        return result
    }
}

7. 总结

到这里，相信你已经掌握了 “下一个更大元素” 问题的解题模板了。除了典型例题之外，大部分题目会将 “下一个更大元素” 的语义隐藏在题目细节中，需要找出题目的抽象模型或转变思路才能找到，这是难的地方。

小彭在 20 年的文章里说过单调栈是一个相对冷门的数据结构，包括参考资料和网上的其他资料也普遍持有这个观点。 单调栈不能覆盖太大的问题域，应用价值不及其他数据结构。 —— 2 年前的文章

2 年后重新思考，我不再持有此观点。我现在认为：单调栈的关键是 “单调性”，而栈只是为了配合问题对操作顺序的要求而搭配的数据结构。 我们学习单调栈，应该当作学习单调性的思想在栈这种数据结构上的应用，而不是学习一种新的数据结构。对此，你怎么看？

下一篇文章，我们来学习单调性的思想在队列上数据结构上的应用 —— 数据结构与算法 #12 使用单调队列解决 “滑动窗口最大值” 问题

更多同类型题目：

版权声明

本文为稀土掘金技术社区首发签约文章，14天内禁止转载，14天后未获授权禁止转载，侵权必究！

参考资料

• LeetCode 专题 · 单调栈 —— LeetCode 出品
• LeetCode 题解 · 739. 每日温度 —— LeetCode 出品
• 第 9 章 · 单调栈 —— liweiwei1419 著
• 单调栈解决 Next Greater Number 一类问题 —— labuladong 著

推荐阅读

数据结构与算法系列完整目录如下（2023/07/11 更新）：

• #1 链表问题总结
• #2 链表相交 & 成环问题总结
• #3 计算器与逆波兰表达式总结
• #4 高楼丢鸡蛋问题总结
• #5 为什么你学不会递归？谈谈我的经验
• #6 回溯算法解题框架总结
• #7 下次面试遇到二分查找，别再写错了
• #8 什么是二叉树？
• #9 什么是二叉堆 & Top K 问题
• #10 使用前缀和数组解决 “区间和查询” 问题
• #11 面试遇到线段树，已经这么卷了吗？
• #12 使用单调队列解决 “滑动窗口最大值” 问题
• #13 使用单调栈解决 “下一个更大元素” 问题
• #14 使用并查集解决 “朋友圈” 问题
• #15 如何实现一个优秀的 HashTable 散列表
• #16 简答一波 HashMap 常见面试题
• #17 二叉树高频题型汇总
• #18 下跳棋，极富想象力的同向双指针模拟

Java & Android 集合框架系列文章: 跳转阅读

LeetCode 上分之旅系列文章：跳转阅读

⭐️ 永远相信美好的事情即将发生，欢迎加入小彭的 Android 交流社群~

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有