單調棧型題目貢獻法
基本模版
這是數組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）
