文章摘要
Deepseek-v3.2

C++ 贡献法与单调栈完全指南：从原理到实战，解决复杂问题的高效技巧

在算法竞赛和编程面试中，我们常常会遇到一些关于数组、序列的复杂问题，例如“寻找所有子数组的最小值之和”或“柱状图中的最大矩形”。暴力枚举虽然直观，但时间复杂度往往难以接受。这时，贡献法 与 单调栈 这两大“神器”的结合，便能为我们提供一种高效而优雅的解决方案。

本指南将带你深入理解这两种思想，并通过C++代码示例，让你彻底掌握这一强大工具组合。

第一部分：理解核心概念

1.1 什么是贡献法？

贡献法 是一种逆向思维。它不直接求解最终答案，而是思考：数组中的每个元素，对最终答案贡献了多少？

  • 传统思路：枚举所有子数组（或子序列），然后计算每个子数组的某个属性（如最小值），最后求和。
  • 贡献法思路：固定一个元素 arr[i]，确定它在哪些子数组中作为最小值（或其他特定角色），然后将这些子数组的数量乘以 arr[i]，即为 arr[i] 对总和的贡献。最后，将所有元素的贡献相加，得到最终答案。

核心思想：化整为零，分而治之。

1.2 什么是单调栈？

单调栈 是一种特殊的栈，其栈内元素始终保持单调性（递增或递减）。它主要用于解决“下一个更大元素”或“上一个更小元素”这类问题。

  • 单调递增栈：栈内元素从栈底到栈顶是递增的。常用于寻找“下一个更小元素”。
  • 单调递减栈：栈内元素从栈底到栈顶是递减的。常用于寻找“下一个更大元素”。

核心价值：利用单调栈，我们可以在 O(n) 的时间复杂度内，为数组中的每个元素快速找到其左右边界，这个边界定义了该元素作为最值的有效范围。

第二部分：为什么是“黄金组合”？

贡献法回答了“每个元素贡献了多少？”的问题，但它需要一个高效的方法来确定每个元素的“统治范围”——即它在哪些子数组里是最小值（或最大值）。

单调栈恰恰完美地回答了“统治范围是什么？”的问题。它能高效地为我们找到每个元素左右两边第一个比它小（或大）的元素的位置，从而精确地界定其作为最值的区间。

因此，单调栈为贡献法提供了计算基础，两者结合，威力无穷。

第三部分：实战应用一：子数组最小值之和

LeetCode 经典题目：907. 子数组的最小值之和

问题描述：给定一个整数数组 arr，求所有子数组的最小值之和。

解法思路（贡献法 + 单调递减栈）

  1. 贡献法视角：总和 S 可以看作是每个元素 arr[i] 乘上它作为最小值的子数组数量的总和。 S = sum( arr[i] * count[i] )，其中 count[i] 是 arr[i] 作为最小值的子数组个数。

  2. 确定统治范围：对于 arr[i]，我们需要找到：

    • left[i]：在 i 左侧，严格小于 arr[i] 的最近元素位置。如果不存在，则为 -1。
    • right[i]：在 i 右侧，小于等于 arr[i] 的最近元素位置。如果不存在，则为 n。 （注意：这里一侧用严格小于，另一侧用小于等于，是为了避免重复计算。当有相同元素时，我们约定由其中一个统一负责包含这些相同元素的区间。）

  3. 计算子数组数量：在 (left[i], right[i]) 这个开区间内，arr[i] 是最小值。那么，以 arr[i] 为最小值的子数组的起点可以从 left[i] + 1 到 i，终点可以从 i 到 right[i] - 1。

    • 起点选择数：i - left[i]
    • 终点选择数：right[i] - i
    • 总子数组数量 count[i] = (i - left[i]) * (right[i] - i)

  4. 使用单调栈：我们可以使用一个单调递增栈来一次性计算出所有 left 和 right 数组。

C++ 代码实现（非Leetcode格式）

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 MOD = 998244353;

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	i64 n;
	cin >> n;
	vector<i64> a(n);
	for (auto& x : a) cin >> x;
	vector<i64> L(n, -1), R(n, n);
	stack<i64> st;

	for (i64 i = 0; i < n; i++) {
		while (!st.empty() && a[st.top()] > a[i]) st.pop();
		if (!st.empty()) L[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()) R[i] = st.top();
		st.push(i);
	}

	i64 ans = 0;
	for (int i = 0; i < n; i++) {
		i64 cnt = (i64)(i - L[i]) * (R[i] - i);
		ans = (ans + a[i] * cnt) % MOD;
	}
	cout << ans << "\n";
	return 0;
}

代码解析：

  • 第一个循环计算 left 数组。栈是递增的，当遇到一个更小的元素时，会弹出栈顶，保证了栈内元素对应的值是从栈底到栈顶递增的。
  • 第二个循环计算 right 数组。我们从右向左遍历，栈同样是递增的，但判断条件用 >，这确保了当有相同元素时，左边的元素能找到正确的右边界（即下一个相同元素的位置），从而避免了重复计算区间。
  • 最后，遍历每个元素，计算其贡献并累加。

时间复杂度：O(n)，每个元素入栈出栈各一次。 空间复杂度：O(n)。

第四部分：实战应用二：柱状图中最大的矩形

LeetCode 经典题目：84. 柱状图中最大的矩形

问题描述：给定一个非负整数数组 heights，表示柱状图的高度，每个柱子的宽度为1。求图中能勾勒出的最大矩形的面积。

解法思路（贡献法 + 单调递增栈）

  1. 贡献法视角：最大矩形面积 S 可以看作是，以每个柱子 heights[i] 为高度的最大矩形的面积中的最大值。 S = max( height[i] * width[i] )，其中 width[i] 是以 heights[i] 为高的矩形的最大宽度。

  2. 确定宽度：以 heights[i] 为高的矩形，其宽度由左右边界决定。左边界是 i 左边第一个高度小于 heights[i] 的柱子，右边界是 i 右边第一个高度小于 heights[i] 的柱子。

    • left[i]：左边第一个小于 heights[i] 的位置。
    • right[i]：右边第一个小于 heights[i] 的位置。
    • 宽度 width[i] = right[i] - left[i] - 1

  3. 使用单调栈：同样使用单调递增栈来一次性计算出所有 left 和 right 数组。

C++ 代码实现

#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> left(n, -1);   // 左边更小柱子的下标
        vector<int> right(n, n);   // 右边更小柱子的下标
        stack<int> st; // 单调递增栈，存储下标

        // 计算 left 边界
        for (int i = 0; i < n; i++) {
            while (!st.empty() && heights[st.top()] >= heights[i]) {
                st.pop();
            }
            if (!st.empty()) {
                left[i] = st.top();
            }
            st.push(i);
        }

        // 清空栈
        while (!st.empty()) st.pop();

        // 计算 right 边界
        for (int i = n - 1; i >= 0; i--) {
            while (!st.empty() && heights[st.top()] >= heights[i]) {
                st.pop();
            }
            if (!st.empty()) {
                right[i] = st.top();
            }
            st.push(i);
        }

        // 计算最大面积
        int maxArea = 0;
        for (int i = 0; i < n; i++) {
            int width = right[i] - left[i] - 1;
            int area = heights[i] * width;
            maxArea = max(maxArea, area);
        }
        return maxArea;
    }
};

代码解析：

  • 逻辑与“子数组最小值之和”几乎完全相同，只是计算贡献的方式从 (值 * 数量) 变成了 (高 * 宽)。
  • 注意边界处理：left[i] 为 -1，right[i] 为 n 时，意味着该柱子可以延伸到数组的边界。

优化版本（一次遍历）：

我们可以通过一次遍历就同时确定左右边界，代码更简洁。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        stack<int> st; // 单调递增栈，存储下标
        int maxArea = 0;

        // 一次遍历处理
        for (int i = 0; i <= n; i++) {
            // 引入一个哨兵高度0，用于在遍历结束后弹出栈中所有元素
            int currentHeight = (i == n) ? 0 : heights[i];

            while (!st.empty() && heights[st.top()] > currentHeight) {
                // 当前柱形的高度是 st.top()，它被 currentHeight 卡住了右边界
                int height = heights[st.top()];
                st.pop();
                // 弹出后，新的栈顶就是它的左边界
                int left = st.empty() ? -1 : st.top();
                int width = i - left - 1;
                maxArea = max(maxArea, height * width);
            }
            st.push(i);
        }
        return maxArea;
    }
};

这个版本是更常见的写法。它在数组末尾添加了一个高度为0的“哨兵”，确保遍历结束时栈内所有元素都能被正确处理弹出。当弹出栈顶元素时，i 是其右边界（第一个比它小的），新的栈顶是其左边界（第一个比它小的）。

第五部分：总结与技巧

核心步骤总结

  1. 识别问题：问题是否与“子数组的最值”、“边界”有关？是否可以通过计算每个元素的贡献来解决？
  2. 定义贡献：明确每个元素在最终答案中扮演的角色（如：作为最小值、最大值）。
  3. 寻找边界：使用单调栈快速找到每个元素作为最值的左右边界。
    • 找最小值范围 -> 使用单调递增栈。
    • 找最大值范围 -> 使用单调递减栈。
  4. 处理重复元素：这是关键！决定一侧用严格比较（< 或 >），另一侧用非严格比较（<= 或 >=），以确保每个子数组只被计算一次。
  5. 计算贡献：根据边界信息，计算每个元素的贡献，并合并得到最终答案。

常见变体与练习

掌握贡献法和单调栈，将使你在面对一系列复杂的数组问题时游刃有余。它们不仅是高效的算法工具，更是培养逆向思维和问题分解能力的绝佳范例。希望这篇指南能成为你算法学习路上的得力助手！