背景问题

给定长度为 $n$ 的数组 $\rm{A}$ ，其每个元素为非负整数，计算其所有连续子序列的最小值之和

问题分析

首先可以很直观的想到，只要遍历 $\rm{A}$ 中的每个元素 $\rm{A[i]}$ ，计算以该元素为最后一个元素的全部连续子序列中最小值的和，记作 $\rm{sum[i]}$ ，最后将 $\rm{sum[0]}$ 到 $\rm{sum[n - 1]}$ 相加就能得到所求的结果。因此解决问题的关键就在于，如何计算 $\rm{sum}$ 数组？

算法设计

考虑对 $\rm{A[j]}$ 计算 $\rm{sum[j]}$ ，有两种情况：1. 对任意的 $0 \leq i < j$ ，都有 $\rm{A[i] \geq A[j]}$ ；2. 存在一个最大的 $i$ ，满足 $0 \leq i < j$ ，使得 $\rm{A[i] < A[j]}$

对任意的 $0 \leq i < j$ ，都有 $\rm{A[i] \geq A[j]}$ ：显然 $\rm{sum[j] = A[j] \times (j + 1)}$
存在一个最大的 $i$ ，满足 $0 \leq i < j$ ，使得 $\rm{A[i] < A[j]}$ ：此时可以将以连续子序列分成两部分考虑，即包括 $\rm{A[i]}$ 的连续子序列和不包括 $\rm{A[i]}$ 的连续子序列。两种情况下的具体分析如下，根据分析此时有 $\rm{sum[j] = sum[i] + A[j] \times (j - i)}$

包括 $\rm{A[i]}$ 的连续子序列：这些连续子序列可以用 $\rm{A[k,j]}$ 描述，其中 $0 \leq k \leq i$ ，而 $\rm{A[k,j]}$ 又可以分成 $\rm{A[k,i]}$ 和 $\rm{A[i + 1,j]}$ 两个部分。根据 $i$ 的选取规则，显然 $\rm{A[k,j]}$ 的最小值只存在于 $\rm{A[k,i]}$ 中，那么这一部分连续子序列的最小值之和其实就是 $\rm{sum[i]}$

不包括 $\rm{A[i]}$ 的连续子序列：这些连续子序列可以用 $\rm{A[k,j]}$ ，其中 $i < k \leq j$ ，根据 $i$ 的选取规则，显然这一部分连续子序列的最小值之和就是 $\rm{A[j] \times (j - i)}$

算法实现

根据算法分析，可知 $\rm{sum}$ 的计算需要从前往后计算，且关键在于如何对任意的 $\rm{A[j]}$ ，找到符合条件的 $\rm{A[i]}$ 。最简单的方法就是对于每个 $j$ ，从 $j - 1$ 开始向 $0$ 逐个判断，这样做的时间复杂度为 $O(n^2)$ 。实际上，只要利用一种数据结构，就能把这一操作的时间复杂度降至 $O(n)$ ，那就是单调栈。单调栈是一种特殊的栈结构，其栈内元素是单调递增或者单调递减的，例如单调递增的单调栈，其构建形式大致如下所示：

stack<int> stack_i;
array<int, 10> arr;
for(i = 0; i < 10; i++)
{
    // 不断弹出栈顶元素，直到栈顶元素指向的原始数组内元素小于待入栈元素指向的原始数组内元素
    while(!stack.empty() && arr[stack_i.top()] >= arr[i])
    {
        stack_i.pop();
    }

    // 待入栈元素入栈
    stack_i.push(i);
}

这种栈有一个特点，即对于每个 $\rm{arr[j]}$ ，在弹出栈顶元素之后，栈顶元素 $i$ 若存在，则其指向的元素一定是原始数组中满足 $\rm{arr[i] < arr[j]}$ 的 $\rm{arr[i]}$ 里最靠近 $\rm{arr[j]}$ 的那个，若栈为空了，则说明 $\rm{arr[j]}$ 是前 $j + 1$ 个元素里最小的。也就是说，利用这一特点，可以在遍历一遍数组，且每个元素至多入栈出栈一次的情况下，对任意的 $\rm{A[j]}$ ，找到符合条件的 $\rm{A[i]}$ 。并且由于每个元素至多入栈出栈一次，时间复杂度仅为 $O(n)$ 。据此，可以写出时间复杂度为 $O(n)$ 的完整算法：

int sumSubarrayMins(vector<int>& A) {
    auto size = A.size();
    vector<int> sums(size);
    stack<int> seqs;
    int i;
    int res;
    
    for(i = 0; i < size; i++)
    {
        while(!seqs.empty() && A[seqs.top()] >= A[i])
            seqs.pop();
        if(seqs.empty()) sums[i] = A[i] * (i + 1);
        else sums[i] = sums[seqs.top()] + A[i] * (i - seqs.top());
        seqs.push(i);
    }

    res = 0;
    for(i = 0; i < size; i++) res += sums[i];
    return (int)res;
}

单调栈的应用

从背景问题的算法设计和实现中可以看到，单调栈可以使得寻找数组中每个元素左边第一个小于它的元素位置的时间复杂度降低至 $O(n)$ ，类似地，以下几种问题都可以用单调栈解决：

寻找数组中每个元素左边第一个小于它的元素位置：该算法在上面已经给出
寻找数组中每个元素左边第一个大于它的元素位置：构建单调递增栈

stack<int> stack_i;
array<int, 10> arr;
array<int, 10> res;
for(i = 0; i < 10; i++)
{
    // 不断弹出栈顶元素，直到栈顶元素指向的原始数组内元素大于待入栈元素指向的原始数组内元素
    while(!stack.empty() && arr[stack_i.top()] <= arr[i]) stack_i.pop();
    
    // 保存arr[i]对应的索引res[i]
    if(stack_i.empty()) res[i] = -1;
    else res[i] = stack_i.top();

    // 待入栈元素入栈
    stack_i.push(i);
}

寻找数组中每个元素右边第一个小于它的元素位置：构建单调递减栈

stack<int> stack_i;
array<int, 10> arr;
array<int, 10> res;
for(i = 10; i >= 0; i--)
{
    // 不断弹出栈顶元素，直到栈顶元素指向的原始数组内元素小于待入栈元素指向的原始数组内元素
    while(!stack.empty() && arr[stack_i.top()] >= arr[i]) stack_i.pop();
    
    // 保存arr[i]对应的索引res[i]
    if(stack_i.empty()) res[i] = 10;
    else res[i] = stack_i.top();

    // 待入栈元素入栈
    stack_i.push(i);
}

寻找数组中每个元素右边第一个大于它的元素位置：构建单调递减栈

stack<int> stack_i;
array<int, 10> arr;
array<int, 10> res;
for(i = 10; i >= 0; i--)
{
    // 不断弹出栈顶元素，直到栈顶元素指向的原始数组内元素大于待入栈元素指向的原始数组内元素
    while(!stack.empty() && arr[stack_i.top()] <= arr[i]) stack_i.pop();
    
    // 保存arr[i]对应的索引res[i]
    if(stack_i.empty()) res[i] = 10;
    else res[i] = stack_i.top();

    // 待入栈元素入栈
    stack_i.push(i);
}

单调索引栈与单调元素栈

上述的四种情况里，单调栈里存储的都是原始数组中某个元素对应的索引，这种单调索引栈是单调递增还是单调递减只和索引的变化方向有关。单调索引栈用于需要索引信息的问题中。上述四类问题如果不需要找到位置，只需要找到每个元素对应的那个元素的值的话，则可以使用直接使用单调元素栈，省去从索引转换到元素值的步骤。对于某一类问题，使用索引栈和元素栈时，栈的增减情况可能会有不同：

寻找数组中每个元素左边第一个小于它的元素位置：
使用索引栈时，遍历数组的方向从左向右，因此为递增栈；使用元素栈时，大于等于当前元素的栈顶元素都被弹出，因此同样为递增栈
寻找数组中每个元素左边第一个大于它的元素位置：
使用索引栈时，遍历数组的方向从左向右，因此为递增栈；使用元素栈时，小于等于当前元素的栈顶元素都被弹出，因此为递减栈
寻找数组中每个元素右边第一个小于它的元素位置：
使用索引栈时，遍历数组的方向从右向左，因此为递减栈；使用元素栈时，大于等于当前元素的栈顶元素都被弹出，因此为递增栈
寻找数组中每个元素右边第一个大于它的元素位置：
使用索引栈时，遍历数组的方向从右向左，因此为递减栈；使用元素栈时，小于等于当前元素的栈顶元素都被弹出，因此同样为递减栈

单调栈的应用与总结