本文主要是介绍LeetCode907. Sum of Subarray Minimums——单调栈，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文章目录
- 一、题目
- 二、题解
一、题目
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 109 + 7.
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 <= arr.length <= 3 * 104
1 <= arr[i] <= 3 * 104
二、题解
class Solution {
public:int sumSubarrayMins(vector<int>& arr) {int mod = 1e9 + 7;long long res = 0;int n = arr.size();stack<int> st;for(int i = 0;i < n;i++){while(!st.empty() && arr[i] <= arr[st.top()]){int cur = st.top();st.pop();int left = st.empty() ? -1 : st.top();res = (res + (long long)(cur - left) * (i - cur) * arr[cur]) % mod;}st.push(i);}while(!st.empty()){int cur = st.top();st.pop();int left = st.empty() ? -1 : st.top();res = (res + (long long)(cur - left) * (n - cur) * arr[cur]) % mod;}return (int) res;}
};
这篇关于LeetCode907. Sum of Subarray Minimums——单调栈的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
