首页 > 其他分享 >Leetcode第907题:子数组的最小值之和(Sum of subarrays minimums )

Leetcode第907题:子数组的最小值之和(Sum of subarrays minimums )

时间:2022-10-28 15:56:26浏览次数:69  
标签:sta minimums int subarrays 元素 栈顶 最小值 区间 907

解题思路

既然我们不能先遍历区间,然后找最小值,那么我们不如顺序倒过来,对于每个值,我们找有多少区间里面,它是最小值。
对于一个数字 A[i] 来说,如果在某个区间 [j, k] 里面它是最小值,那么 [j, k] 包含 A[i] 的子数组的最小值也一定是 A[i] 。所以我们只需要找出最大的那个区间,使得 A[i] 是最小值就行了。
另一个性质是,左右端点 j 和 k 是相互独立的,不会影响,因为 [i, k] 的改变并不会改变 [j, i] 的最小值。所以我们只需要分别求出 A[i] 往左和往右的最远距离就行了。
因为往左和往右求解方法是类似的,所以我们只需要看一个方向就行了。同样不能遍历一遍,不然就和暴力法没区别了嘛。这时候就要介绍神器了——单调栈。
单调栈是一个栈,后进先出,里面的元素是单调递增或递减的。而在这题里面,我们要求的是 A[i] 左边最远的距离,等价于求左边第一个比它小的数字 A[j] 。而 A[j+1], ..., A[i] 都大于等于 A[i] ,所以都可以作为符合要求区间的左端点。
这里单调栈只需要维护一个单调上升的子序列就行了,遍历到一个数 A[i] 的时候,如果栈顶的元素大于等于 A[i] ,那么就出栈,直到第一个小于 A[i] 的数 A[j] 为止,那么 A[i] 为最小值的区间左端点可选择数量为 j - i。为什么这样是对的呢?因为 A[j] 是栈里面第一个小于 A[i] 的数,而 A[j] 后面的数都大于 A[j] ,这样才不会把 A[j] 顶出栈。而如果栈是空的,就说明 A[i] 前面的所有元素都大于等于它,那么所有区间都符合条件了。
而右边最大的范围同理可以求得,但是这里有个需要注意的地方!如果存在两个相同的数,这么算不是会导致同一个区间在两个数的位置处计算两次吗?所以要稍稍改进一下,既然向左计算的时候,已经包含了相等的值了,那么向右计算就要排除掉了。也就是从右往左计算右边最远范围的时候,只能计算右边第一个小于等于它的位置,而向左是计算第一个小于它的位置。这样就不会重复计算了。

核心代码如下:

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        long ret = 0;
        stack<int> sta;
        int mod = int(1e9 + 7);
        for (int i=0; i <= arr.size(); i++) {
            while (!sta.empty() && arr[sta.top()] > arr[i]) {
                //栈不空,且栈顶元素大于入栈元素时,要出栈并计算arr[sta.top()]的辐射
                //范围和以该元素为中心的子数组和
                int cent = sta.top();    //出栈(下标),辐射范围中心点位置
                sta.pop();
                
                int left = !sta.empty() ? sta.top() : -1;   //辐射范围左区间是此时
                //栈顶元素(下标),最后一个元素没有左边范围
                int right = i;  //辐射范围右
                ret = (ret + long( (cent-left)*(right-cent)*arr[cent] )) % mod;
            }
            sta.push(i);    //栈顶元素小于入栈元素,入栈下标值
        }
        
        return int(ret);
    }
};

标签:sta,minimums,int,subarrays,元素,栈顶,最小值,区间,907
From: https://www.cnblogs.com/hql5/p/16836341.html

相关文章