题目:
给你一个整数数组 nums 。nums 中,子数组的 范围 是子数组中最大元素和最小元素的差值。
返回 nums 中 所有 子数组范围的 和 。
子数组是数组中一个连续 非空 的元素序列。
解题代码:
暴力解法
func subArrayRanges(nums []int) int64 { var ans int64 for i, num := range nums { minVal, maxVal := num, num for _, v := range nums[i+1:] { if v < minVal { minVal = v } else if v > maxVal { maxVal = v } ans += int64(maxVal - minVal) } } return ans }
这是官方的题解,我刚开始以为可以这样写
func subArrayRanges(nums []int) int64 { var ans int64 sort.Ints(nums) for i, num := range nums { for _, v := range nums[i+1:] { ans += int64(v - num) } } return ans }
但是不行,得到的结果会比正确答案小。
这是因为我选择遍历是让每个数都与比它小的数相减,而子数组的范围不会两个数相减就OK了,例如 [4,1,-3] ,有两个包含4,且包含1的子数组[4,1]、[4,1,-3],这就会导致只计算 4 - 1而跳过计算 4 - (-3),从而导致得到的结果偏小。