【LeetCode】 907 子数组的最小值之和
Decrisption
Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr. Since the answer may be large, return the answer modulo \(10^9\) + 7.
Input
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
Constraints
\(1\leq arr.length\leq3*10^4\)
\(1\leq arr[i]\leq3*10^4\)
Solution
思路:
方法一:暴力计算
直接计算每一个子数组中的最小值并全部相加,时间复杂度为\(O\)(\(n^2\)),显然会超时。
class Solution {
public:
int MOD=1e9+7;
int sumSubarrayMins(vector<int>& arr) {
int n=arr.size();
int ans=0;
for(int i=0;i<n;i++){
for(int j=0;j<=i;j++){
int min=*min_element(arr.begin()+j,arr.begin()+i+1);
ans+=min;
ans%=MOD;
}
}
return ans;
}
};
方法二:两次单调栈+贡献法
方法一中由于重复计算了许多次相同的最小值,所以我们要想办法免去复杂计算。对于数组中的每一个元素,其都会在最终的答案中有一个贡献值。该贡献值可以看成是每一个元素作为子数组的最小元素的次数。
注意到:对于某一个元素\(x\),假定其下标为\(i\),如果x是某一个子数组的最小值,该子数组的左端点为\(left\),右端点为\(right\),那么在[\(left\),\(right\)]范围内所有包含\(x\)的子数组的最小值都为x,x的贡献为\(arr[i]\)\(*\)(\(i-left\))\(*\)(\(right-i\))。所以我们要找到每一个元素左侧第一个小于该元素的位置\(left\)和右侧第一个小于该元素的位置\(right\)。这样在区间\((left,right)\)范围内包含\(x\)的子数组的最小值可以确定为x,x的贡献值为\(arr[i]*(i-left)*(right-i)\).
class Solution {
public:
int MOD=1e9+7;
typedef long long ll;
int sumSubarrayMins(vector<int>& arr) {
int n=arr.size();
ll ans=0;
vector<ll> left(n,-1); //左边界为-1
vector<ll> right(n,n); //右边界为n
stack<ll> stk;
for(int i=0;i<n;i++){
while(!stk.empty()&&arr[stk.top()]>arr[i]){
stk.pop();
}
if(!stk.empty()){
left[i]=stk.top();
}
stk.push(i);
}
while(!stk.empty()) stk.pop();
for(int i=n-1;i>=0;i--){
while(!stk.empty()&&arr[stk.top()]>=arr[i]){
stk.pop();
}
if(!stk.empty()){
right[i]=stk.top();
}
stk.push(i);
}
for(ll i=0;i<n;i++){
ans+= (ll)arr[i]*(i-left[i])*(right[i]-i);
ans%=MOD;
}
return ans;
}
};
时间复杂度:\(O(n)\)
空间复杂度:\(O(n)\)
最新文章
- QuicKHit
- 【LINUX】VI相关命令
- Bootstrap_列表组
- php 使用curl模拟登录人人(校内)网
- python基础知识4——collection类——计数器,有序字典,默认字典,可命名元组,双向队列
- UVA11324 强连通+dp记忆化搜索
- Delphi / C++ Builder 使用 UDT ( UDP-based Data Transfer ) 4.11
- IOS开发之UINavigationBar
- Javascript Prototype __proto__ constructor 三者的关系
- Jmeter之Bean shell学习(一)
- 接口测试——HttpClient工具的https请求、代理设置、请求头设置、获取状态码和响应头
- 如何合理封装你的轮子、飞机、大炮(以封装OkHttp为例)
- java学习之—数组的曾删改查
- load加载层-layui
- 服务注册与发现---eureka
- WingIDE 常用快捷键
- crc16.c
- 将DevExpress.Utils.ImageCollection变量的image导出
- mysql explicit_defaults_for_timestamp参数
- Apache Hive 存储方式、压缩格式