文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你一個整數數組 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 -10^9 <= nums[i] <= 10^9

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/sum-of-subarray-ranges
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 單調棧，獲取每個數字作為最大或者最小的左右極限位置
• 單獨考慮每個數字可以作為最大值或者最小值的次數，到左右極限位置處的個數相乘種組合

class Solution:def subArrayRanges(self, nums: List[int]) -> int:def getRange(nums, neg):nums_ = copy.deepcopy(nums)if neg:for i in range(len(nums)):nums_[i] = -nums_[i] # 找最小值的左右區間，取個負數，邏輯跟正數一樣L, R = list(range(len(nums))), list(range(len(nums)))q = []for i in range(len(nums)):while len(q) and nums_[q[-1]] < nums_[i]:q.pop()L[i] = q[-1]+1 if len(q) else 0q.append(i)q = []for i in reversed(range(len(nums))):while len(q) and nums_[q[-1]] <= nums_[i]:q.pop() # 注意上下只能有一個 = 號R[i] = q[-1]-1 if len(q) else (len(nums)-1)q.append(i)return L, RL1, R1 = getRange(nums, neg=False)L2, R2 = getRange(nums, neg=True)ans = 0for i in range(len(nums)):# print(L1[i], R1[i], L2[i], R2[i])ans += (R1[i]-i+1)*(i-L1[i]+1)*nums[i]-(R2[i]-i+1)*(i-L2[i]+1)*nums[i]return ans

140 ms 15.2 MB Python3

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 2104. 子数组范围和（单调栈）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。