Leetcode—907.子数组的最小值之和【中等】

2023每日刷题（四十二）

Leetcode—907.子数组的最小值之和

算法思想

参考自y神思想

实现代码

class Solution {
public:int sumSubarrayMins(vector<int>& arr) {long long ans = 0;const int mod = 1e9+7;int n = arr.size();stack<int> st;vector<int> left(n, -1);vector<int> right(n, n);for(int i = 0; i < n; i++) {int t = arr[i];while(!st.empty() && arr[st.top()] >= t) {st.pop();}if(!st.empty()) {left[i] = st.top();}st.push(i);}st = stack<int>();for(int i = n - 1; i >= 0; i--) {int t = arr[i];while(!st.empty() && arr[st.top()] > t) {st.pop();}if(!st.empty()) {right[i] = st.top();}st.push(i);}for(int i = 0; i < n; i++) {ans += 1LL * (i - left[i]) * (right[i] - i) * arr[i] % mod;ans %= mod;}return ans;}
};

运行结果

之后我会持续更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持！