[游戏开发]LeetCode 2104. Sum of Subarray Ranges - 亚马逊高频题3

You are given an integer array?nums. The?range?of a subarray of?nums?is the difference between the largest and smallest element in the subarray.

Return?the?sum of all?subarray ranges of?nums.

A subarray is a contiguous?non-empty?sequence of elements within an array.

Example 1:

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.

Example 2:

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

Example 3:

Input: nums = [4,-2,-3,4,1]
Output: 59
Explanation: The sum of all subarray ranges of nums is 59.

Constraints:

• 1 <= nums.length <= 1000
• -109?<= nums[i] <= 109

Follow-up:?Could you find a solution with?O(n)?time complexity?

题目对一个数组的子数组的范围range做了定义，即子数组中最大值与最小值的差。数组的子数组是数组中一个非空且连续的序列。要求返回一个给定数组nums的所有子数组的范围range的和。

显然可以用暴力解法，即找出所有子数组，再找出每个子数组的最大值和最小值。但是暴力解法肯定不是出题人所要的解法。

暴力解法是要算出每个子数组的最大值和最小值的差然后再求和，换种思路，要是能算出所有子数组的最大值总和与最小值总和然后再求差，那么其结果是一样的。于是题目就可以变成先找出所有子数组的最大值的和，再找出所有子数组的最小值的和。印象中LeetCode中有类似的题。

那么该如何快速计算所有子数组的最大值和或最小值和呢？先以求所有子数组的最大值和为例，由于每个子数组必然是以数组中某一个数为最大值，反过来想，如果能找出数组中以每一个数为最大值的所有子数组，也就可以算出所有子数组的最大值和。例如以第i个数为最大值的子数组的个数为k，那么这部分子数组的最大值和为nums[i] * k。

于是题目进一步演变成如何算出k，以nums[i]为中心向左找到第一个比nums[i]大的数的位置记为l，向右找到第一个比nums[i]大的数的位置记为r，那么以nums[i]为最大值的子数组个数就为k=nums[i] * (i - k) * (r - i)。具体算法可以单调递减栈来实现（与LeetCode 42. Trapping Rain Water有点 类似）。只要碰到比栈顶更小的数就放进堆栈，当遇到比栈顶大的数，就要计算以栈顶数为最大值的所有子数组个数，算完弹出栈顶数，继续比较计算当前数与栈顶数，直到当前数不大于栈顶数就停止然后把当前数入栈。要注意栈为空的情况，以及数组遍历完栈里可能还有数要继续处理。

注：最小值和求法是一样的，只要把单调递减栈换成单调递减栈即可。

class Solution:
    def subArrayRanges(self, nums: List[int]) -> int:
        n = len(nums)
        st = []
        
        minSum = 0
        for i in range(n):
            while st and nums[i] < nums[st[-1]]:
                mid = st.pop()
                j = st[-1] if st else -1
                minSum += nums[mid] * (mid - j) * (i - mid)
            st.append(i)
        while st:
            mid = st.pop()
            j = st[-1] if st else -1
            minSum += nums[mid] * (mid - j) * (n - mid)
        maxSum = 0
        for i in range(n):
            while st and nums[i] > nums[st[-1]]:
                mid = st.pop()
                j = st[-1] if st else -1
                maxSum += nums[mid] * (mid - j) * (i - mid)
            st.append(i)        
        while st:
            mid = st.pop()
            j = st[-1] if st else -1
            maxSum += nums[mid] * (mid - j) * (n - mid )
        
        return maxSum - minSum

?