数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++子数组最小值之和
假设我们有一个整数数组A。我们需要找到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]，所以最小值为[3,1,2,4,1,1,2,1,1,1]，它们的和为17。
为了解决这个问题，我们将遵循以下步骤：
m := 1 x 10^9 + 7
定义两个方法，add() 将接收a, b并返回 (a mod m + b mod m) mod m，mul() 将接收a, b并返回 (a mod m * b mod m) mod m
主方法将接收数组A，定义一个栈st，并设置n := 数组A的大小
定义两个大小为n的数组left，并用-1填充，另一个是right，用n填充
设置ans := 0
对于i从0到n – 1
当st不为空且A[栈顶] >= A[i]时，从st中删除元素
如果st不为空，则设置left[i] := st的栈顶
将i插入到st中
当st不为空时，删除st中的所有元素
对于i从n – 1到0
当st不为空且A[栈顶] >= A[i]时，从st中删除元素
如果st不为空，则设置right[i] := st的栈顶
将i插入到st中
对于i从0到n – 1
leftBound := i – left[i] + 1, rightBound := right[i] – 1 – i
contri := 1 + leftBound + rightBound + (leftBound * rightBound)
ans := add(ans 和 mul(contri, A[i]))
返回ans
示例 (C++)
让我们来看下面的实现以更好地理解：
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli MOD = 1e9 + 7;
class Solution {
public:
lli add(lli a, lli b){
return (a % MOD + b % MOD) % MOD;
}
lli mul(lli a, lli b){
return (a % MOD * b % MOD) % MOD;
}
int sumSubarrayMins(vector<int>& A) {
stack <int> st;
int n = A.size();
vector <int> left(n, -1);
vector <int> right(n, n);
int ans = 0;
for(int i = 0; i < n; i++){
while(!st.empty() && A[st.top()] >= A[i]){
st.pop();
}
if(!st.empty())left[i] = st.top();
st.push(i);
}
while(!st.empty())st.pop();
for(int i = n - 1; i >= 0; i--){
while(!st.empty() && A[st.top()] > A[i]){
st.pop();
}
if(!st.empty())right[i] = st.top();
st.push(i);
}
for(int i = 0; i < n; i++){
int leftBound = i - (left[i] + 1);
int rightBound = (right[i] - 1) - i;
int contri = 1 + leftBound + rightBound + (leftBound * rightBound);
ans = add(ans, mul(contri, A[i]));
}
return ans;
}
};
main(){
vector<int> v = {3,1,2,4};
Solution ob;
cout << (ob.sumSubarrayMins(v));
}输入
[3,1,2,4]
输出
17
浏览量 182
