[TOC]

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

2104. 子数组范围和

对于很久没有刷题的我来说，突然开始也开始刷题了，不为别的，已经习惯参与掘金的活动了，同时也可以促进自己再回顾一下算法题，毕竟长时间不练，真的就生疏了

本月开始刷题了，尝试写题解，希望能够对你有帮助

一、题目描述：

给你一个整数数组 nums 。nums 中，子数组的 范围 是子数组中最大元素和最小元素的差值。

返回 nums 中 所有 子数组范围的 和 。

子数组是数组中一个连续 非空 的元素序列

二、思路分析：

1、这道题考察了什么思想？你的思路是什么？

看了这题的描述和示例，我们应该得到了如下几个信息

• 从给出的数组中，要找到所有的子数组，子数组中的元素顺序是要和原有数组元素顺序是保持一致的
• 对于每一个子数组，我们需要找到该子数组中的最大值，和最小值，并计算差值
• 需要将所有子数组的计算的结果，求和

对于这个子数组，需要注意的地方是，要是连续的，非空的

如果我们认为可以向上述这样组成子数组那么思考方向就是错误的，这里一定需要注意

根据以上已知信息，我们可以一步一步的来推导，先看如何找到子数组

由于是需要在子数组中找到最大数和最小数的差值，那么子数组中只有一个元素的情况，我们就直接忽略，首先根据题意，子数组要非空，那么若子数组只有 1 个元素，则最大数和最小数的差值是 0

我们可以用上述示例 3 来进行演示：

4 ， -2 ，-3，4， 1
复制代码

根据上图，我们不难理解，

• 就是先指定左边第 1 个元素为起始位置，然后不停的向右扩，扩充到的每一个子数组，计算最大值和最小值的差值，直到扩充到数组长度后
• 再从左边起始的第 2 个元素，再继续向右扩
• 最终，当起始元素指到数组的最右边的一个元素的时候，则查找完毕
• 最终将所有的子数组的差值求和

2、尝试编码

那么，根据上述的图示和逻辑，咱们不难写出类似于这样的代码

这样的实现方式，对于大多数用例也是可以满足的，但是对于数量大一点的用例，实际情况是通过了 56 个用例，但是对于数据复杂一点的用例就会出现时间超限的情况

仔细查看咱们写的代码，实际上是使用了 3 层 for 循环 ，这在生产环境中肯定是不允许的

因此，咱们一定有优化的空间

3、思考和探索

上述对于计算每一个子数组的最大值和最小值的做法是一样的，筛选出的子数组的方式也是一样的，那么，我们是否可以换一种思路来看看这个题，想办法筛选出子数组的 max ，和 min 分别对应放置，最终，直接计算对应的数据差值，再求和即可，这样就可以杜绝 3 个 for 循环了

例如上图，我们第一步，以及将 [4,-2] 最大值 和 最小值计算出来，那么 [4,-2,-3] 子数组的时候，只需要和 [4,-2] 的结果进行比较和计算即可

例如计算 [4,-2,-3] 最大值的时候，只需要 将 [4,-2] 子数组中的最大值 和 -3 进行比较，那么一定是 [4,-2,-3] 的最大值

最小值的计算逻辑也是一样，其他的子数组计算逻辑也是保持一致

总结：

如果你还有更多的思考、分析、总结，通通都加上来吧~

今天就到这里，学习所得，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是小魔童哪吒，欢迎点赞关注收藏，下次见~