sum-of-subarray-ranges

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

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

Return the sum of all subarray ranges of <code>nums</code>.

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

&nbsp;
Example 1:

<pre>
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.</pre>

Example 2:

<pre>
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.
</pre>

Example 3:

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

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 1000</code></li>
	<li><code>-109 &lt;= nums[i] &lt;= 109</code></li>
</ul>

&nbsp;
Follow-up: Could you find a solution with <code>O(n)</code> time complexity?

subArrayRanges

Sum of Subarray Ranges

Next Greater Element I

next-greater-element-i

下一个更大元素 I

Sum of Subarray Minimums

sum-of-subarray-minimums

子数组的最小值之和

Number of Visible People in a Queue

number-of-visible-people-in-a-queue

队列中可以看到的人数

Count Number of Homogenous Substrings

count-number-of-homogenous-substrings

统计同质子字符串的数目

Sum of Total Strength of Wizards

sum-of-total-strength-of-wizards

巫师的总力量和

Stack

Array

Monotonic Stack

给你一个整数数组 <code>nums</code> 。<code>nums</code> 中，子数组的 范围 是子数组中最大元素和最小元素的差值。

返回 <code>nums</code> 中 所有 子数组范围的 和 。

子数组是数组中一个连续 非空 的元素序列。

&nbsp;

示例 1：

<pre>
输入：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</pre>

示例 2：

<pre>
输入：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
</pre>

示例 3：

<pre>
输入：nums = [4,-2,-3,4,1]
输出：59
解释：nums 中所有子数组范围的和是 59
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 1000</code></li>
	<li><code>-109 &lt;= nums[i] &lt;= 109</code></li>
</ul>

&nbsp;

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