房产网站建设网站推广,江干网站建设,大连建设网水电官网查询,中国建设教育协会网站查题目要求
给定一个整数数组 arr#xff0c;求 min(b) 的总和#xff0c;其中 b 的范围涵盖 arr 的每个#xff08;连续#xff09;子数组。由于答案可能很大#xff0c;因此返回答案模数
Example 1:
Input: arr [3,1,2,4]
Output: 17
Explanation:
Subarrays are [3]…题目要求
给定一个整数数组 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。这意味着从 L1 到 i 的所有位置arr[i] 都是最小的。 右侧范围类似地我们找出在 arr[i] 右侧的第一个比 arr[i] 小的元素。设这个位置为 R。这意味着从 i 到 R-1 的所有位置arr[i] 都是最小的。
知道这两个位置后我们可以计算以 arr[i] 为最小值的子数组数量。这个数量等于 arr[i] 左侧和右侧可扩展的位置数的乘积。
特别注意处理数值相同时的情况。只需要在处理左边界或者有边界时候加入一个等号即可。始终认为出现相同值时右边的更小。
代码
class Solution {
public:int sumSubarrayMins(vectorint arr) {stackint s;int result 0;int n arr.size();vectorint 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这个题目的思路和代码是在它的指导下写出来的还挺好用的。
时空复杂度
