单调栈型题目贡献法
基本模版
这是数组a中的
首先我们要明白什么叫做贡献，在一个数组b={1,3,5}中，连续包含1的连续子数组为{1}，{1,3}，{1,3,5}，一共有三个，这三个数一共能组成6个连续子数组，而其中3个子数组都有1，那么就代表了1的贡献值为3,也就是6*1/2
明白了这个概念我们就好写了，假设a数组中有{1,3,5,4,7}，需要求每一个子数组中最小值的和，
我们可以利用上述的贡献法来写，以计算左边界为例，从左到右遍历 arr，同时用某个合适的数据结构维护遍历过的元素，并及时移除无用的元素，这个数据结构就是栈。
-
当前遍历到元素 a[i]a[i]
-
如果发现 a[i]≤a[j]a[i]≤a[j]（其中 a[j]a[j] 是栈顶元素）
-
那么对于之后任何比 a[j]a[j] 大的元素 xx，必然也满足 x>a[i]x>a[i]
-
由于 a[i]a[i] 比 a[j]a[j] 更靠近后面的元素 xx，所以 a[j]a[j] 将永远不会再被用作边界值
-
因此可以直接将 a[j]a[j] 弹出栈（它已经"没有任何作用了"）
这是三次遍历的模版
-
#include <vector> #include <stack> using namespace std;class Solution {const int MOD = 1e9 + 7; public:int sumSubarrayMins(vector<int>& arr) {int n = arr.size();vector<int> left(n, -1); // 左边第一个比当前元素小的位置vector<int> right(n, n); // 右边第一个小于或等于当前元素的位置stack<int> st;// 计算左边界for (int i = 0; i < n; ++i) {while (!st.empty() && arr[st.top()] >= arr[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() && arr[st.top()] > arr[i]) {st.pop();}if (!st.empty()) {right[i] = st.top();}st.push(i);}long ans = 0;for (int i = 0; i < n; ++i) {ans += (long)arr[i] * (i - left[i]) * (right[i] - i);ans %= MOD;}return (int)ans;} };还是一次遍历的模版：
#include <vector> #include <stack> using namespace std;class Solution {const int MOD = 1e9 + 7; public:int sumSubarrayMins(vector<int>& arr) {long ans = 0L;arr.push_back(-1); // 添加哨兵，确保最终清空栈stack<int> st;st.push(-1); // 初始化栈底哨兵for (int r = 0; r < arr.size(); ++r) {// 维护单调递增栈while (st.size() > 1 && arr[st.top()] >= arr[r]) {int i = st.top(); // 当前处理的柱子索引st.pop();// 计算贡献值：(i - left_bound) * (right_bound - i) * arr[i]ans += (long) arr[i] * (i - st.top()) * (r - i);ans %= MOD; // 防止溢出}st.push(r);}arr.pop_back(); // 恢复原数组（可选）return (int) ans;} };
典型例题：
907. 子数组的最小值之和 - 力扣（LeetCode）
本文参考了力扣的灵山爱抚茶的题单分享｜【算法题单】单调栈（矩形面积/贡献法/最小字典序）- 讨论 - 力扣（LeetCode）
