计算所有子区间 最大值乘 最小值 的 和 (单调栈)

计算所有子区间最大值乘以最小值的和，通常使用单调栈（Monotonic Stack）的数据结构来解决这个问题。单调栈的主要原理是利用栈的单调性，即如果栈内的元素是非递减的，那么栈顶元素一定是这段区间的最大值；如果栈内元素非递增，那么栈顶元素就是最小值。

以下是一个简单的C++实现思路：

1. 初始化两个变量：`maxSum`表示当前子区间最大值与最小值的乘积，初始为0；`stack`用于存储每个子区间的最小子区间。
2. 遍历数组，用两个指针`left`和`right`分别从左到右移动：
a. 如果`right`到达数组末尾，说明已经形成一个子区间，此时计算`maxValue * minValue`并加到`maxSum`上。若`stack`为空或当前元素大于等于栈顶元素，则将其压入栈中；否则，将栈中的元素弹出直到栈顶元素小于当前元素，然后将当前元素和剩余栈顶元素一起压入栈中。
b. 如果`left`比`right`慢，说明找到了一个新的可能的最大值，更新`maxValue`为当前元素，但不需要做其他操作。
3. 当遍历完成后，`maxSum`就是所求的结果。

下面是示例代码：

#include <vector>
#include <stack>

int maxProduct(std::vector<int>& nums) {
    int n = nums.size();
    if (n <= 1) return 0;

    int left = 0, right = 0;
    int maxValue = nums[0], minValue = nums[0];
    std::stack<int> stack;
    stack.push(minValue);
    int maxSum = 0;

    while (right < n - 1) {
        // 更新区间
        if (nums[right + 1] >= minValue) {
            minValue = nums[right + 1];
            stack.push(minValue);
        } else {
            while (!stack.empty() && nums[right + 1] < stack.top()) {
                maxValue = std::max(maxValue, stack.top());
                minValue = std::min(minValue, stack.top());
                stack.pop();
            }
            minValue = nums[right + 1];
            stack.push(minValue);
        }

        // 计算结果
        maxSum += maxValue * minValue;

        // 移动左右指针
        right++;
        if (right < n) {
            maxValue = std::max(maxValue, nums[right]);
        }
    }

    return maxSum;
}