单调栈
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 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
解释：
同理，首先，套一下单调栈的适用条件
- 这是一个数组，这里的条件比较隐晦，可以这样理解，数组里的元素遇到比自己大的或者相等的，可以向右勾勒，但是遇到比自己小的，不能向右勾勒，然后求每个元素的勾勒面积的最大值，是满足第一个条件的。
- 如果遇到比自己小的，不能向右勾勒，可以统计此元素的勾勒面积吗，那就要看左边了，左边也都是有序且小于等于此元素的，宽度只与元素位置有关，高度只与此元素值有关，可以统计。统计后排除此元素，会对后面元素的统计有影响吗，这里要注意，如果排除对后面元素是可能有影响的，因为后面元素的统计宽度与此元素的位置可能有关，比如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;
}
