What is the main strategy for Sum of Subarray Ranges?

The key is using monotonic stacks to find previous and next smaller and greater elements, then aggregating each element's contribution to all subarray ranges.

Can this solution handle arrays with duplicate elements?

Yes, properly designed monotonic stacks account for duplicates when computing previous/next smaller and greater indices.

Why avoid nested loops for this problem?

Nested loops lead to O(n^2) complexity, which is inefficient for arrays up to length 1000, while monotonic stacks achieve O(n).

Is there a space-efficient version?

Monotonic stacks require O(n) space, which is optimal for tracking all previous and next min/max elements simultaneously.

How does stack-based state management help in subarray range problems?

It allows efficient determination of subarray boundaries for each element's max/min contribution, reducing redundant comparisons and achieving linear time calculation.

#2104

Medium

auto_awesome栈·状态

LeetCode 题解工作台

子数组范围和

给你一个整数数组 nums 。 nums 中，子数组的范围是子数组中最大元素和最小元素的差值。返回 nums 中所有子数组范围的和。子数组是数组中一个连续非空的元素序列。示例 1：输入： nums = [1,2,3] 输出： 4 解释： nums 的 6 个子数组如下所示： …

数组栈单调栈

题目描述

给你一个整数数组 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⁹ <= nums[i] <= 10⁹

进阶：你可以设计一种时间复杂度为 O(n) 的解决方案吗？

lightbulb

解题思路

方法一：暴力枚举

循环遍历 $i$ ，作为子数组的起始位置。对于每个 $i$ ，遍历每个 $j$ 作为子数组的终止位置，此过程中不断求解子数组的最大值、最小值，然后累加差值到结果 ans 中。

最后返回 ans 即可。

时间复杂度 $O(n^2)$ 。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def subArrayRanges(self, nums: List[int]) -> int:
        ans, n = 0, len(nums)
        for i in range(n - 1):
            mi = mx = nums[i]
            for j in range(i + 1, n):
                mi = min(mi, nums[j])
                mx = max(mx, nums[j])
                ans += mx - mi
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) because each element is pushed and popped at most once from each stack. Space complexity is O(n) for the stacks tracking previous and next smaller or greater elements.
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Expect candidates to recognize the pattern of using monotonic stacks for range-based subarray calculations.
question_mark
Look for attempts to reduce nested loops by tracking element contributions to multiple subarrays.
question_mark
Candidates should discuss edge cases where elements repeat and correctly handle inclusive counting of subarrays.

warning

常见陷阱

外企场景

error
Miscounting subarrays by not correctly combining previous and next smaller/greater indices.
error
Using nested loops leading to O(n^2) complexity, which fails for large arrays.
error
Failing to handle duplicates, causing overcounting or undercounting in contribution calculations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute sum of subarray maximums only, emphasizing the same monotonic stack principle.
arrow_right_alt
Compute sum of subarray minimums only, applying the stack-based state tracking in reverse.
arrow_right_alt
Find the maximum subarray range instead of the sum, which requires similar min/max tracking but selects the largest difference.

help

常见问题

外企场景

继续练习

#1996 游戏中弱角色的数量 #1944 队列中可以看到的人数 #2281 巫师的总力量和