LeetCode 907: 子数组的最小值之和-单调栈的运用 ｜Sum of Subarray Minimums-Fantasy use of Monotonic Stack

Tags: #MonoStack #Stack

Problem Description

Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr. Module the answer (10^9+7).

Example:

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.

Problem Analysis & Transformation

We are asked to get each subarray’s min, and sum them up. The straightforward way is to calculate the minimum value of each subarray, and sum them up.

We can transform this question to another one. For each element i(i is the index), find the number of subarrays whose minimum element is that element, mark as #i.

In the above example:
#0=1, the range is [3], the subarray is [3].
#1=6, the range is [3,1,2,4], those subarrays are [3,1], [1], [1,2], [1,2,4], [3,1,2], [3,1,2,4].
#2=2, the range is [2,4], those subarrays are [2], [2,4].
#3=1, the range is [4], the subarray is [4].

So the total sum is each element’s value times the number of subarrays it corresponding to. totalSum=sum(arr[i]*#i).
totalSum=1*3+6*1+2*2+4*1=17

If there are two same elements, they will find same subarrays. We deal with this situation as follows:
Every element’s subarrays’ left edge is the first element that small or equal to it(if there is none, mark as -1), the right edge is the first element that strictly less than it(if non, mark as n: length of arr).

Here is an example:
arr = [3,1,5,1,2,4]
The subarray range of the right 1([3,1,5,_1_,2,4]) is [1,2,4]. The subarray range of the left 1([3,_1_,5,1,2,4]) is [3,1,5,1,2,4]. So that those two 1’s subarrays won’t be intersected.

So the method to find subarray range is:

Given an element e, find the first element less than or equal to e to the left as the left boundary, and the first element strictly less than e to the right as the right boundary. The range does not contain boundaries.

The proof maybe incomplete…
The proof is divided into two aspects:

If there is a subarray sArr that is not contained. Assume the minimum element of sArr is e. In the find subarray step, all subarray which has no element small than e should be found. That’s a contradiction. Even there are two same elements in sArr, at least one has contained this subarray.

Assume there is a subarray sArr which is found by two different element e and v(different in index, may same in value).

Case 1: e!=v
Since e=min(sArr) and v=min(sArr), so e=v, that’s a contradiction.

Case 2: e=v
As explained in above boundary situation, as index of e is not equal to v, w.o.l.g, assume index of e is smaller than index of v. So the range of e‘s subarray should be [..e..v...], while the range of v‘s subarray should be [..v...] which does contain element e and even left. So e and v won’t find a same subarray(because the subarray range is different).

In last part, we find the subarray range of an elements e, where each element in the subarray is equal or bigger than e.

So the problem comes: How to count the number of the subarrays of that range?

It’s quite easy. The left side elements number is idx(e)-leftBound, they can form idx(e)-leftBound subarrays(remember subarray must contain e). The right side elements number is rightBound-idx(e), they can form rightBound-idx(e) subarrays. The left and right sides are combined in pairs to produce all subarrays: #idx(e)=(idx(e)-leftBound)*(rightBound-idx(e)).

So the answer is totalSum=sum(arr[i]*#i).

Review of problem transformation process

To find next smaller value, use mono-stack!

Coding Details

We need to find the first element less than or equal to each element to the left, and the first element strictly less than each element to the right. Problem like this, finding the one-side small, should be solved using monotonic stack.

We can use an increasing stack, when pushing an element, popping until the peek element of the stack is smaller than or equal to the pushing element. Every popped element’s right side is also determined, just like Largest Rectangle in Histogram previous blog.

When popping an element, we know it’s left bound, the peek element of stack, we also know it’s right bound, the pushing element. So we add its contribution to the answer.

The answer maybe quite large, so we need to module (10^9+7) when calculating.

Since there may be no smaller element in left, so we set it to -1. Same as the right side, set it to n.

In the pushing process, we also push -1 and n to the stack, the value corresponding to it is infinitesimal. We pushing -1 first because every element are larger than it, so it can be proper boundary when popping. We pushing n finally because every element are also larger than it(except the first -1), so when pushing n, all elements of arr will be popped out, and their right boundary are n. That’s understandable, because when pushing n, there is only a monotonically increasing sequence left in the stack.

The code as follows:

public class Solution {
    int[] arr;
    int n;

    public int sumSubarrayMins(int[] arr) {
        int MOD = 1_000_000_007;

        // handle input arr's error
        if (arr == null || arr.length == 0) {
            return 0;
        }
        this.arr = arr;
        n = arr.length;

        long ans = 0L;
        Deque increStack = new ArrayDeque<>();
        // add index -1 and n into the process(their value are minInfinity) so that
        // don't need to consider boundary situation.

        for (int i = -1; i

Original: https://www.cnblogs.com/liuzhch1/p/16421111.html
Author: liuzhch1
Title: LeetCode 907: 子数组的最小值之和-单调栈的运用 ｜Sum of Subarray Minimums-Fantasy use of Monotonic Stack