广州购物商城网站,网站优化建设上海,测速网站开发,前端网站开发流程图907. 子数组的最小值之和
给定一个整数数组 arr#xff0c;找到 min(b) 的总和#xff0c;其中 b 的范围为 arr 的每个#xff08;连续#xff09;子数组。
由于答案可能很大#xff0c;因此 返回答案模 10^9 7 。 思路同乘法原理 LeetCode 828. 统计子串中的唯一字符-…907. 子数组的最小值之和
给定一个整数数组 arr找到 min(b) 的总和其中 b 的范围为 arr 的每个连续子数组。
由于答案可能很大因此 返回答案模 10^9 7 。 思路同乘法原理 LeetCode 828. 统计子串中的唯一字符-CSDN博客
遍历arr[i]时找左边第一个比arr[i]的下标L找右边第一个比arr[i]小的下标R。
那么区间左端点取 L1,i
区间右端点取i,R-1。
注意如果出现重复元素这样找会重复计算。
如[1,2,3,4,2] 子数组2,3,4,2在遍历时会加两次2所以防止重复计算左边不能取等或右边不能取等。
使用单调栈来找左边第一个比当前数小的下标(数)。
【单调栈】单调栈模板_单调栈 模板_暮色_年华的博客-CSDN博客
使用left[i]表示小于arr[i] 左边的第一个下标
使用right[i]表示小于等于arr[i]右边的第一个下标
class Solution {
public:int sumSubarrayMins(vectorint arr) {const int MOD1e97;//使用单调栈//left[i]表示arr[i]左边第一个比arr[i]小的下标//right[i]表示arr[i]右边第一个比arr[i]小的下标stackintst;int narr.size();vectorintleft(n,-1);vectorintright(n,n);for(int i0;in;i){while(!st.empty()arr[st.top()]arr[i])st.pop();if(st.empty())left[i]-1;else left[i]st.top();st.push(i);}while(!st.empty())st.pop();for(int in-1;i0;i--){while(!st.empty()arr[st.top()]arr[i])st.pop();if(st.empty())right[i]n;else right[i]st.top();st.push(i);}long res0L;for(int i0;in;i){res(long)(i-left[i])*(right[i]-i)*arr[i];}return res%MOD;}};
注意取模
long res0
res(long)
res%MOD;
