讨论/《春招冲刺班 - 7 天刷题挑战》 - 907. 子数组的最小值之和/
《春招冲刺班 - 7 天刷题挑战》 - 907. 子数组的最小值之和
共 9 个回复
  • 直接枚举所有的子区间成本太大,O(n^2)
  • 考虑计算每个数的贡献
  • 比如: 3 4 1 2 6 7 5 8 3
  • 观察 5 作为最小值能贡献多少次,[6-5], [7-5], [5-5], [6-8], [7-8], [5-8]
  • 只要找到 5 左边和右边第一个比它小的数的位置就能知道它的贡献次数
  • 用单调栈计算每个数左右两边比它小的数的位置
  • 注意怎么消除重复数的影响
  • 比如:3 4 1 6 5 7 5 8 1, 方便描述, 我将第二个 5 写成 55
  • 第一个 5 对应 [6,5] - [5,7,55,8],第二个 5 对应[6,5,7,55] - [55,8]
  • 显然 [6-55], [6-8], [5-55], [5-8] 重复计算了两次
  • 我们可以计算左边第一个小于等于它的位置, 右边小于它的位置
  • 那么第一个 5 对应 [6,5] - [5,7,55,8],第二个 5 对应 [7,55] - [55,8]
  • 这就不会有问题了
class Solution {
    private static final int mod = 1000000007;
    public int sumSubarrayMins(int[] arr) {
        int[] dp = new int[arr.length];
        int[] stack = new int[arr.length+1];
        int len = 0, sum = 0; stack[0] = -1;
        for (int i = 0;i < arr.length; ++i){
            while (len != 0 && arr[i] < arr[stack[len]]) len -= 1;
            dp[i] = stack[len];
            stack[++len] = i;
        }
        stack[len = 0] = arr.length;
        for (int i = arr.length-1;i >= 0; --i){
            while (len != 0 && arr[i] <= arr[stack[len]]) len -= 1;
            sum += 1l*arr[i]*(stack[len]-i)*(i-dp[i]) % mod;
            if (sum >= mod) sum -= mod;
            stack[++len] = i;
        }
        return sum;
    }
}
3

核心思路:
1. 对每个数arr[i]的贡献,需要知道从i位置开始,连续往左边大于arr[i]数的个数left_num,和连续往右边大于arr[i]数的个数right_num,然后arr[i]的贡献就是,sum += (arr[i] * left_num * right_num)。
2. 另外,若arr[i] == arr[i + 1], 我们认为 arr[i] > arr[i + 1]。

const int mod = 1e9 + 7;
class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        long ans = 0;
        arr.push_back(0);  // 用于清空栈
        stack<int> greater_stack;  // 递增栈
        for (int i = 0; i < arr.size(); ++i)
        {
            while (!greater_stack.empty() && arr[i] <= arr[greater_stack.top()])  // 处理重复数字
                // 这里使用等于号,由于prev_index默认为前面的值,故数字相等时,后面的更小。
            {
                // 由于下标 i 的值 小于 index,栈递增,可以知道栈中下一个元素也小于 index,(栈空则见下面)
                // 根据这个条件,可以推测出比下标 index 的值大的范围,即这两个值(见prev_index, next_index)的中间。
                int index = greater_stack.top();  
                greater_stack.pop();
                // next_index 的值为 当前所遍历到的数字
                int next_index = i;
                // prev_index 的值为 -1(栈空的话)
                int prev_index = -1;
                // 栈非空,则说明为栈元素下标
                if (!greater_stack.empty())
                    prev_index = greater_stack.top();
                // 知道范围,则计算元素左右两边的个数,包括自身
                int left_num = index - prev_index;
                int right_num = next_index - index;
                // 将被计算的次数为 左右两边的组合数,再乘于 index所在的arr值
                ans += (left_num * right_num * long(arr[index]));  
                ans %= mod;
            }
            greater_stack.push(i);
        }

        return ans;
    }
};
2

算出左右各有多少个数是用当前的值进行计算的,然后相乘【即组合】,算出次数后,与当前值相乘,加起来就完事了。
代码如下:

class Solution {
    private long contributionValue(int[] arr, int index){
        int left = index - 1, right = index + 1;
        //calculate left
        while(left >= 0 && arr[left] > arr[index])
            left--;
        //calculate right
        while(right < arr.length && arr[right] >= arr[index])
            right++;
        return (index - left) * (right - index);
    }
    public int sumSubarrayMins(int[] arr) {
        long sum = 0;
        for(int i = 0; i < arr.length; i++)
            sum += contributionValue(arr,i) * arr[i];
        return (int)(sum % 1000000007);
    }
}
2

单调栈,解决中心寻找边界问题适用
class Solution {

//设i元素左边有n个大于i元素的元素,右边有m个大于i元素的元素,则最小值为i的子集合一共1+n+m+n*m个,所以问题转化为寻找每个i元素的左右边界问题
//单调栈,当前元素小于栈顶元素则将栈中所有大于当前元素的元素全部弹出
//被弹出元素的右边界一定是当前便利的i,左边界一定是栈中下一个元素
//为防止栈中无元素和保证全部遍历,将原始数组前后各填充一个0
public int sumSubarrayMins(int[] arr) {
    Deque<Integer> stack = new LinkedList<>();
    long res = 0;
    int[] array = new int[arr.length+2];
    //头尾填充0
    for(int i=0;i<arr.length;i++) array[i+1] = arr[i];
    for(int i=0;i<array.length;i++){
        int k = i;
        while(!stack.isEmpty()&&array[i]<array[stack.peek()]){
            k=stack.pop();
            int t = stack.peek();
            long m = (k-t-1)*(i-k-1);
            res+=array[k];
            if(k-t-1>0)res+=array[k]*(k-t-1);
            if(i-k-1>0)res+=array[k]*(i-k-1);
            if(m>0) res+=array[k]*m;
            res%=1000000007;
        }
        stack.push(i);
    }
    return (int)res;
}

}

1
class Solution {
    public int sumSubarrayMins(int[] arr) {
        LinkedList<Integer> stack = new LinkedList<>();
        //如果嫌判空麻烦,可以预加一个 stack.addLast(-1);
        int res = 0, now = 0;
        for (int i = 0; i < arr.length; i++) {
            while (!stack.isEmpty() && arr[stack.getLast()] > arr[i]) {
                int x = stack.removeLast();
                int y = stack.isEmpty() ? -1 : stack.getLast();
                //这里的范围是 (y, x]
                //此时范围内最小值是arr[x],arr[i]比arr[x]小,更新now
                now += (arr[i] - arr[x]) * (x - y);
            }
            stack.addLast(i);
            //加入arr[i]
            now += arr[stack.getLast()];
            res += now;
            res %= 1000000007;
        }
        return res;
    }
}

利用单调栈找到最小值的左右边界,能组成的子数组数量为(idx - left) * (right - idx)

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        res = 0
        stack = [-1]
        for i in range(len(arr)):
            while stack[-1] != -1 and arr[stack[-1]] >= arr[i]:
                idx = stack.pop()
                res += arr[idx] * (idx - stack[-1]) * (i - idx)
            stack.append(i)
        while stack[-1] != -1:
            idx = stack.pop()
            res += arr[idx] * (idx - stack[-1]) * (len(arr) - idx)
        return res % (10 ** 9 + 7)

更新了,你再看看

厉害,解释一下

参与“7天刷题挑战”的童鞋欢迎点击问卷加入专属社群哦~
2月1日-7日,字节跳动工程师直播刷题等你来围观