資料結構
網路
關係資料庫管理系統 (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
