广告片制作哪家好班级优化大师官方网站
题目要求
给定一个整数数组 arr，求 min(b) 的总和，其中 b 的范围涵盖 arr 的每个（连续）子数组。由于答案可能很大，因此返回答案模数
Example 1:
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.
Example 2:
Input: arr = [11,81,94,43,3] Output: 444
思路
找出数组的全部组合数，加和并返回mod()之后的结果。我们只需要找出所有的组合然后加到一起。但是这样至少需要O(N^2)的时间复杂度，会超时。
然后又想到不需要真正求出子数组，只需要求出子数组的最小值即可。同时发现子数组不能交换顺序。因此想到用单调栈解决本题。
-
左侧范围：我们需要找出在
arr[i]左侧的第一个比arr[i]小的元素。设这个位置为L。这意味着从L+1到i的所有位置，arr[i]都是最小的。 -
右侧范围：类似地，我们找出在
arr[i]右侧的第一个比arr[i]小的元素。设这个位置为R。这意味着从i到R-1的所有位置，arr[i]都是最小的。
知道这两个位置后，我们可以计算以 arr[i] 为最小值的子数组数量。这个数量等于 arr[i] 左侧和右侧可扩展的位置数的乘积。
特别注意：处理数值相同时的情况。只需要在处理左边界或者有边界时候加入一个等号即可。（始终认为出现相同值时，右边的更小）。
代码
class Solution {
public:int sumSubarrayMins(vector<int>& arr) {stack<int> s;int result = 0;int n = arr.size();vector<int> left(n), right(n);long long mod = 1000000007; // 10^9 + 7for (int i = 0; i < n; ++i) {while (!s.empty() && arr[s.top()] >= arr[i]) {right[s.top()] = i;s.pop();}s.push(i);}while (!s.empty()) {right[s.top()] = n;s.pop();}for (int j = n-1; j >= 0; --j) {while (!s.empty() && arr[s.top()] > arr[j]) {left[s.top()] = j;s.pop();}s.push(j);}while (!s.empty()) {left[s.top()] = -1;s.pop();}for (int i = 0; i < n; ++i) {cout << i << " " << left[i] << " " << right[i] << " " << arr[i] << endl;result += ((long long)(i - left[i]) * (right[i] - i) % mod * arr[i] % mod) % mod;result %= mod;}return result;}
};特别感谢GPT的Code Tutor，这个题目的思路和代码是在它的指导下写出来的，还挺好用的。
时空复杂度
