sum-of-subarray-minimums

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given an array of integers arr, find the sum of <code>min(b)</code>, where <code>b</code> ranges over every (contiguous) subarray of <code>arr</code>. Since the answer may be large, return the answer modulo <code>109 + 7</code>.

&nbsp;
Example 1:

<pre>
Input: arr = [3,1,2,4]
Output: 17
Explanation: 
Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. 
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.
Sum is 17.
</pre>

Example 2:

<pre>
Input: arr = [11,81,94,43,3]
Output: 444
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= arr.length &lt;= 3 * 104</code></li>
	<li><code>1 &lt;= arr[i] &lt;= 3 * 104</code></li>
</ul>

sumSubarrayMins

Sum of Subarray Minimums

Sum of Subarray Ranges

sum-of-subarray-ranges

子数组范围和

Sum of Total Strength of Wizards

sum-of-total-strength-of-wizards

巫师的总力量和

Stack

Array

Dynamic Programming

Monotonic Stack

给定一个整数数组 <code>arr</code>，找到 <code>min(b)</code> 的总和，其中 <code>b</code> 的范围为 <code>arr</code> 的每个（连续）子数组。

由于答案可能很大，因此 返回答案模 <code>10^9 + 7</code> 。

 

示例 1：

<pre>
输入：arr = [3,1,2,4]
输出：17
解释：
子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。 
最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。</pre>

示例 2：

<pre>
输入：arr = [11,81,94,43,3]
输出：444
</pre>

 

提示：

<ul>
	<li><code>1 <= arr.length <= 3 * 104</code></li>
	<li><code>1 <= arr[i] <= 3 * 104</code></li>
</ul>