2104. 子数组范围和
https://leetcode.cn/problems/sum-of-subarray-ranges/
难度中等208
给你一个整数数组 nums 。nums 中，子数组的 范围 是子数组中最大元素和最小元素的差值。
返回 nums 中 所有 子数组范围的 和 。
子数组是数组中一个连续 非空 的元素序列。
示例 1：
输入：nums = [1,2,3] 输出：4 解释：nums 的 6 个子数组如下所示： [1]，范围 = 最大 - 最小 = 1 - 1 = 0 [2]，范围 = 2 - 2 = 0 [3]，范围 = 3 - 3 = 0 [1,2]，范围 = 2 - 1 = 1 [2,3]，范围 = 3 - 2 = 1 [1,2,3]，范围 = 3 - 1 = 2 所有范围的和是 0 + 0 + 0 + 1 + 1 + 2 = 4
示例 2：
输入：nums = [1,3,3] 输出：4 解释：nums 的 6 个子数组如下所示： [1]，范围 = 最大 - 最小 = 1 - 1 = 0 [3]，范围 = 3 - 3 = 0 [3]，范围 = 3 - 3 = 0 [1,3]，范围 = 3 - 1 = 2 [3,3]，范围 = 3 - 3 = 0 [1,3,3]，范围 = 3 - 1 = 2 所有范围的和是 0 + 0 + 0 + 2 + 0 + 2 = 4
示例 3：
输入：nums = [4,-2,-3,4,1] 输出：59 解释：nums 中所有子数组范围的和是 59
提示：
1 <= nums.length <= 1000-109 <= nums[i] <= 109
进阶：你可以设计一种时间复杂度为 O(n) 的解决方案吗？
class Solution {
public long subArrayRanges(int[] nums) {
long ans = 0;
for(int i=0;i<nums.length-1;i++)
{
int max = nums[i];
int min = nums[i];
for(int j=i;j<nums.length;j++)
{
if(max<nums[j]) max = nums[j];
if(min>nums[j]) min = nums[j];
ans += max-min;
}
}
return ans;
}
} 
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/68999.html
