C语言之单调栈

单调栈

What

单调栈也是栈的一种，满足先进后出的原则，另外，单调栈中的元素是有序的，分为两种

• 单调递增栈：单调递增栈就是从栈底到栈顶数据是从大到小

• 单调递减栈：单调递减栈就是从栈底到栈顶数据是从小到大

现在有一组数10，3，7，4，12。从左到右依次入栈，则如果栈为空或入栈元素值小于栈顶元素值，则入栈；否则，如果入栈则会破坏栈的单调性，则需要把比入栈元素小的元素全部出栈。单调递减的栈反之。

• 10入栈时，栈为空，直接入栈，栈内元素为10。

• 3入栈时，栈顶元素10比3大，则入栈，栈内元素为10，3。

• 7入栈时，栈顶元素3比7小，则栈顶元素出栈，此时栈顶元素为10，比7大，则7入栈，栈内元素为10，7。

• 4入栈时，栈顶元素7比4大，则入栈，栈内元素为10，7，4。

• 12入栈时，栈顶元素4比12小，4出栈，此时栈顶元素为7，仍比12小，栈顶元素7继续出栈，此时栈顶元素为10，仍比12小，10出栈，此时栈为空，12入栈，栈内元素为12。

Why

单调栈在解决一些问题时，比暴力循环方法要简单的多，比如遇到，求一个数组在满足元素比较条件下的统计数据时，可以考虑使用单调栈的做法，典型的就是后面第一次出现大于或者小于当前元素，要计算什么什么的时候。

How

适用单调栈的几个条件：

• 求一个数组在满足元素比较条件下的统计数据，比如求和，求面积等

• 由比较条件推出的单调栈的类型，然后栈中新添加的元素不符合时，可以对当前及其前向元素进行单独统计后出栈，且不影响后续元素统计。

伪代码如下：

// 此处一般需要给数组最后添加结束标志符，来满足全部出栈
for (遍历这个数组)
{
    if (栈空 || 栈顶元素大于等于当前比较元素)
    {
        入栈;
    } else {
        while (栈不为空 && 栈顶元素小于当前元素) {
            栈顶元素出栈;
            更新结果;
        }
        当前数据入栈;
    }
}
// 如果没有结束标志符，此处要一般要单独判断全部出栈

Example

视野总和

先上题目和代码

/*
描叙：有n个人站队，所有的人全部向右看，个子高的可以看到个子低的发型，给出每个人的身高，问所有人能看到其他人发现总和是多少。
输入：4 3 7 1
输出：2
解释：个子为4的可以看到个子为3的发型，个子为7可以看到个子为1的身高，所以1+1=2
*/
#define STACK_NUM_MAX 500

int VisionSumGet(int *arr, int arrSize)
{
    int stack[STACK_NUM_MAX] = {0}; /* 记录元素位置的单调栈 */
    int top = -1; /* 此单调栈栈顶的索引, 初始位为-1, 栈为空*/
    int sum = 0;

    for (int i = 0; i < arrSize; i++) { /* 遍历数组 */
        while ((top >= 0) && (arr[i] >= arr[stack[top]])) { /* 栈不为空, 且遇到数组元素相等或者大于栈顶对应的数组元素, 则看不到了，进行统计 */
            sum += (i - stack[top] - 1); /* 统计栈顶对应的数组元素看到的人数，并累加*/
            top--; /* 栈顶元素出，判断下一个栈顶元素是否该统计累加 */
        }
        
        top++; /* 把当前的数组元素索引入栈 */
        stack[top] = i;
    }

    /* 最后还要进行一次计算 */
    while (top >= 0) {
        sum += (arrSize - stack[top] - 1);
        top--;
    }

    return sum;
}

首先，套一下单调栈的适用条件

• 这是一个数组，数组里的元素均向自己看，能看到的是比自己小的，不能看到的是比自己大的或者相等的，而且是要求每个元素能看到的所有元素的个数，显然满足第一个条件。
• 一个元素右边能看到的是比自己小的，如果右边有个比自己大的或者相等的，那么是不是可以统计此元素的情况，统计后，把此元素排除，是不是不会影响其右边元素。因为统计数据与该元素的位置相关，如果我们记录元素位置，显示是符合第二个条件的。

其他可以对照代码注释进行理解。

柱状图中的最大矩形

描述：

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

解释：

Snipaste_2022-09-04_16-25-50.png
Snipaste_2022-09-04_16-26-03.png

同理，首先，套一下单调栈的适用条件

• 这是一个数组，这里的条件比较隐晦，可以这样理解，数组里的元素遇到比自己大的或者相等的，可以向右勾勒，但是遇到比自己小的，不能向右勾勒，然后求每个元素的勾勒面积的最大值，是满足第一个条件的。
• 如果遇到比自己小的，不能向右勾勒，可以统计此元素的勾勒面积吗，那就要看左边了，左边也都是有序且小于等于此元素的，宽度只与元素位置有关，高度只与此元素值有关，可以统计。统计后排除此元素，会对后面元素的统计有影响吗，这里要注意，如果排除对后面元素是可能有影响的，因为后面元素的统计宽度与此元素的位置可能有关，比如2 1 5 6 2 3，2 > 1, 统计2然后排除，2的位置将丢失，在统计1的时候，1是可以勾勒2的位置的。那怎么办，只需要保留2的位置就行了，试想如果2和1之间有多个2，我们应该保留哪一个？我们应该保留距离1最左边的那个2的位置就行了，这样计算1的宽度才是正确的，为了保证有序性，我们把2统计完成后，我们把1左边的2全部排出，然后保留一个最左边位置的且把它的值修改成1，当前的1也不需要进行入栈了，因为它的面积肯迪东比修改成1的那个面积统计的要小。

结合代码，可以好好理解一下：

/*
柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
*/

#define STACK_NUM_MAX 100000

int largestRectangleArea(int *heights, int heightsSize)
{
    int stack[STACK_NUM_MAX] = {0}; /* 记录元素位置的单调栈 */
    int top = -1; /* 此单调栈栈顶的索引, 初始位为-1, 栈为空*/
    int max = 0;
    int area = 0;

    for (int i = 0; i < heightsSize; i++) { /* 遍历数组 */
        /* 栈为空, 或者遇到的元素大于等于栈顶对应的元素, 还可以继续向右勾勒*/
        if ((top < 0) || (heights[i] >= heights[stack[top]])) {
            top++;
            stack[top] = i;
            continue;
        }

        /* 栈不为空, 且遇到的元素小栈顶对应的元素, 统计栈顶对应的元素的面积*/
        while ((top >= 0) && (heights[i] < heights[stack[top]])) {
            area = heights[stack[top]] * (i - stack[top]);
            if (area > max) {
                max = area;
            }
            top--; /* 统计栈顶后出栈 */
        }
        /* 保留最后一次的栈顶, 并修改对应的元素的值为当前遇到的元素值, 当前的元素值也不必入栈, 因为它统计的面积必然小一些*/
        top++;
        heights[stack[top]] = heights[i];
    }

    /* 最后还要进行一次计算 */
    while (top >= 0) {
        area = heights[stack[top]] * (heightsSize - stack[top]);
        if (area > max) {
            max = area;
        }
        top--;
    }

    return max;
}