超过时间限制:我如何在Javascript中优化我的代码?

Question

我正试图解决leetcode上的Sum of Subarray Ranges问题，它给了我Time Limit Exceeded，所以我猜我的代码没有优化好，需要更有效的解决方案。但是我不太擅长它，所以具体来说，我如何在我的代码中删除两个for-loops。

Ques1:Sum of Subarray Ranges

给定一个整数数组nums。nums子数组的范围是子数组中最大元素和最小元素之间的差。返回nums的所有子数组范围的和。子数组是数组中连续的非空元素序列。

的例子:

Input: nums = [1,2,3]
Output: 4
Explanation: The 6 subarrays of nums are the following:
[1], range = largest - smallest = 1 - 1 = 0 
[2], range = 2 - 2 = 0
[3], range = 3 - 3 = 0
[1,2], range = 2 - 1 = 1
[2,3], range = 3 - 2 = 1
[1,2,3], range = 3 - 1 = 2
So the sum of all ranges is 0 + 0 + 0 + 1 + 1 + 2 = 4.

问题联系测试用例:52/71

var subArrayRanges = function(nums) {
let maxSub=0;
for(let i=0; i<nums.length; i++){
let arr=[];
arr.push(nums[i])
for(let j=i+1; j<nums.length; j++){
arr.push(nums[j]);
maxSub=maxSub+(Math.max(...arr)) - (Math.min(...arr));
}
}
return maxSub
};

我如何优化我的代码，使它可以运行所有的测试用例?

Answer 1

优化部分的提示:当j-循环获得一个新元素时，只有该元素可以影响给定子数组的最小/最大值。因此，您实际上不必构建子数组并对其运行实际的min()/max()调用，只需存储其最小值和最大值(这是内部循环开始时相同的[i]元素)，并使用传入的新元素([j]元素)比较和更新它们:

var subArrayRanges = function(nums) {
let maxSub=0;
for(let i=0; i<nums.length; i++){
let min=nums[i],max=nums[i];
for(let j=i+1; j<nums.length; j++){
if(nums[j]<min)min=nums[j];
if(nums[j]>max)max=nums[j];
maxSub=maxSub+max-min;
}
}
return maxSub
};