题目链接：2104. 子数组范围和
假设有 $m$ 个子数组，最终的表达式为 $m$ 个等式 $\sum_{j=1}^{m}{\max_j - \min_j}$ 之和。
若数组中第 $i$ 个数 $n_i$：
- 在 $cnt_{max, i}$ 个子数组中充当最大值，则在上述等式中以 $\max_j$ 的形式出现 $cnt_{max, i}$ 次；
- 如果在 $cnt_{min, i}$ 个区间中充当最小值，则在最终等式中以 $\min_j$ 形式出现 $cnt_{min, i}$ 次。
可统计 $n_i$ 作为子数组最大值的次数 $cnt_{max, i}$ 和作为最小值的次数 $cnt_{min, i}$，$(cnt_{max, i} - cnt_{min, i}) \times n_i$ 的结果就是 $n_i$ 在上述加和式中的贡献。
使用单调栈计算 $cnt_{max, i}$ 和 $cnt_{min, i}$:
- $cnt_{max, i}$：找到 $n_i$ 左右最近的『大于 $n_i$』的位置，记作 $l$ 和 $r$，那么 $n_i$ 作为子数组最大值的次数是 $(i-p)\times (q-i)$ 个；
- $cnt_{min, i}$：找到 $n_i$ 左右最近的『小于 $n_i$』的位置，记作 $l$ 和 $r$，那么 $n_i$ 作为子数组最大值的次数是 $(i-p)\times (q-i)$ 个。
from typing import List
class Solution:
def cnt(self, nums: List[int], is_min: bool):
lft, rgt, lstk, rstk = [], [], [], []
for i in range(len(nums)):
while lstk and (nums[lstk[-1]] >= nums[i] if is_min else nums[lstk[-1]] <= nums[i]): lstk.pop()
lft.append(-1 if not lstk else lstk[-1])
lstk.append(i)
for i in range(len(nums) - 1, -1, -1):
while rstk and (nums[rstk[-1]] > nums[i] if is_min else nums[rstk[-1]] < nums[i]): rstk.pop()
rgt.append(len(nums) if not rstk else rstk[-1])
rstk.append(i)
return [(i - l) * (r - i) for i, (l, r) in enumerate(zip(lft, rgt[::-1]))]
def subArrayRanges(self, nums: List[int]) -> int:
print(self.cnt(nums, False), self.cnt(nums, True))
return sum((ma - mi) * n for ma, mi, n in zip(self.cnt(nums, False), self.cnt(nums, True), nums))