LeetCode-907.子数组的最小值之和

这里是题目描述：LeetCode-907.子数组的最小值之和

本题给定一个整数数组A，求A的所有（连续）子数组的最小值的和，直观上可以用暴力法：列出A的所有子数组，分别求出这些子数组的最小值，再分别将这些最小值相加。但是通过分析时间复杂度：列举出所有子数组需要 O(n²) 的时间复杂度，求一个子数组的最小值需要 O(n) 时间复杂度，因此整体需要 O(n³) 的时间复杂度，会超出时间限制，提交无法通过。我们需要时间效率更优的解法

本题可以转化为：求A中的每个数字是A的几个子数组的最小值，只要知道了它是几个子数组的最小值，就可以将每个数字和它们对应的子数组个数相乘，乘积的和就是所求的最小值之和。例如：

A=[3,1,2,4]

数字3是这些子数组的最小值：[3] 共1个
数字1是这些子数组的最小值：[1]、[3,1]、[1,2]、[3,1,2]、[1,2,4]、[3,1,2,4] 共6个
数字2是这些子数组的最小值：[2]、[2,4] 共2个
数字4是这些子数组的最小值：[4] 共1个

所以子数组的最小值之和 = 3x1+1x6+2x2+4x1 = 17

那么如何求一个数字是几个子数组的最小值呢？我们只需求这个数字在A中位于它左边比它大的数字的个数以及位于它右边比它大的数字个数。以上面的A为例，对于数字1，在A中位于它左边且比它大的数字有1个，位于它右边且比它大的数字有2个，再考虑到数字1本身，因此以1为最小值的子数组个数为(1+1)x(2+1) = 2x3 = 6

那么由该如何计算一个数字在数组A中比它左右两边小的数字的个数？我们在遍历数组过程中使用 栈 这种数据结构：

• 首先定义栈帧结构，每个栈帧有属性val、insertTime和smallerRight。val记录该栈帧代表的数组中数字的值；insertTime记录它入栈的时刻，即当前遍历到的数组的下标；smallerRight记录为与它左边且它小于的数字个数
• 当遍历到一个数字是，创建一个val为当前数字、insertTime是当前数组下标、smallerRight初始化为0的栈帧，然后让栈帧入栈；不断弹出栈顶的val比它小的栈帧，直到栈为空或栈顶的val不小于它的val；为它的smallerRight加1并且加上被弹出栈帧的smallRight，因为比弹出栈帧小的数字肯定也小于待入栈栈帧。而弹出的栈帧计算i-insertTime，表示位于弹出栈帧右边的且大于弹出栈帧的数字个数-1，其中i是数组当前下表，于是最小值是弹出栈帧val的子数组个数为(smallerRight+1)*(i-insertRight)，将它加到最终结果上
• 遍历完数组后，依次弹出栈中剩下的栈帧，并分别计算它们的(smallerRight+1)*(i-insertRight)加到最终结果上

题解代码：

public class Solution {
    public static void main(String[] args) {
        int[] A={3,2,1,4};
        Solution obj=new Solution();
        System.out.println(obj.sumSubarrayMins(A));
    }
    public int sumSubarrayMins(int[] A) {
        Stack<StackNode> stack=new Stack<>();
        int res=0;
        int m=(int)Math.pow(10,9)+7;
        for(int i=0;i<A.length;i++)
        {
            StackNode node=new StackNode(A[i],i);
            while(!stack.isEmpty())
            {
                StackNode topNode=stack.peek();
                if(topNode.val>node.val)
                {
                    node.smallerRight+=(topNode.smallerRight+1);
                    int outTime=i;
                    res+=(topNode.val*(1+topNode.smallerRight)*(outTime-topNode.insertTime));
                    res=res%m;
                    stack.pop();
                }
                else
                {
                    break;
                }
            }
            stack.push(node);
        }
        while(!stack.isEmpty())
        {
            StackNode topNode=stack.pop();
            int outTime=A.length;
            res+=(topNode.val*(1+topNode.smallerRight)*(outTime-topNode.insertTime));
            res=res%m;
        }
        return res;
    }
}
class StackNode //用来存入栈的栈帧类
{
    int val;
    int insertTime; //进栈时间
    int smallerRight; //位于它右边且比它大的元素个数
    StackNode(int val,int insertTime)
    {
        this.val=val;
        this.insertTime=insertTime;
        this.smallerRight=0;
    }
}

时间复杂度：O(n)
空间复杂度：O(n)