沈阳网站制作机构,湖南响应式官网建设哪里有,网站正能量不用下载直接进入主页可以吗,佛山有哪些公司文章目录1. 题目2. 解题1. 题目
给定一个整数数组 A#xff0c;找到 min(B) 的总和#xff0c;其中 B 的范围为 A 的每个#xff08;连续#xff09;子数组。
由于答案可能很大#xff0c;因此返回答案模 10^9 7。
示例#xff1a;
输入#xff1a;[3,1,2,4]
输出找到 min(B) 的总和其中 B 的范围为 A 的每个连续子数组。
由于答案可能很大因此返回答案模 10^9 7。
示例
输入[3,1,2,4]
输出17
解释
子数组为 [3][1][2][4][3,1][1,2][2,4][3,1,2][1,2,4][3,1,2,4]。
最小值为 3124112111和为 17。提示
1 A 30000
1 A[i] 30000来源力扣LeetCode 链接https://leetcode-cn.com/problems/sum-of-subarray-minimums 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目 天池 在线编程 所有子数组之和排列组合 LeetCode 891. 子序列宽度之和数学
分别找到每个数作为最小值的左右边界一边遇到大的停止一边遇到大于等于的停止然后左右组合的种数相乘就是 A[i] 的贡献次数
class Solution {
public:int sumSubarrayMins(vectorint A) {int n A.size();vectorint L(n, -1), R(n, -1);stackint s;for(int i 0 ; i n; i){while(!s.empty() A[s.top()] A[i])s.pop();L[i] (s.empty() ? 0 : s.top()1);s.push(i);}while(!s.empty()) s.pop();for(int i n-1 ; i 0; --i){while(!s.empty() A[s.top()] A[i])//两次等号只能取一次 [71,55,82,55]否则答案有重复s.pop();R[i] (s.empty() ? n-1 : s.top()-1);s.push(i);}int ans 0, mod 1e97;for(int i 0; i n; i){// cout L[i] R[i] endl;ans (ans 1LL*(i-L[i]1)*(R[i]-i1)*A[i]%mod)%mod;}return ans;}
};248 ms 42.4 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
