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] 的最大值
最小值的计算逻辑也是一样，其他的子数组计算逻辑也是保持一致
那么，我们可以推算出如下这样的表格
按照上述的方式，将子数组的 max 放到 big 表格中，min 放到 small 表格中
[4,-2]，计算出 max 为 4 放到 big 表格中，min 为 -2 放到 small 表格中
[4,-2,-3]，计算出 max 为 4 放到 big 表格中，min 为 -3 放到 small 表格中
同理可以得出上述第一行的最大值和最小值， 其余行依次类推，最终得出如下表格：
源码如下：
func subArrayRanges(nums []int) int64 { length := len(nums) big := make([][]int, length) small := make([][]int, length) // small 表格 和 big 表格 ，对角线是 nums 数组元素 for i := 0; i < length; i++ { big[i] = make([]int, length) big[i][i] = nums[i] small[i] = make([]int, length) small[i][i] = nums[i] } // 分别绘制 small 表格，和 big 表格 for i := 1; i < length; i++ { for j := 0; j+i < length; j++ { big[j][j+i] = max(big[j][j+i-1], nums[j+i]) small[j][j+i] = min(small[j][j+i-1], nums[j+i]) } } var sum int for i := 0; i < length; i++ { for j := i + 1; j < length; j++ { sum += big[i][j] - small[i][j] } } return int64(sum) } func max(a, b int) int { if a > b { return a } return b } func min(a, b int) int { if a < b { return a } return b }
当然，这样显的代码行数有点多，但是没有关系，咱们仔细思考一下，就不难理解官方的题解了
原理和我们上述推理过程一致，按照顺序找到子数组，后一个数组的计算参数，依赖于上一个子数组的结果
四、总结：
本题考察对应数组的应用，遍历子数组并进行相应的计算，这种方式时间复杂度是 O(n^2) , 空间复杂度是 O(1)
今天就到这里，学习所得，若有偏差，还请斧正
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
