笔者在做leetcode的题(下一个出现的最大数字)时，接触到了单调栈这一种数据结构，经过研究之后，发现单调栈在解决某些问题时出奇的好用，下面是对单调栈的性质和一些典型题目。

从名字上就听的出来，单调栈中存放的数据应该是有序的，所以单调栈也分为单调递增栈和单调递减栈

• 单调递增栈：数据出栈的序列为单调递增序列
• 单调递减栈：数据出栈的序列为单调递减序列

ps：这里一定要注意所说的递增递减指的是出栈的顺序，而不是在栈中数据的顺序

模拟实现一个递增单调栈：

现在有一组数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。

stack<int> st;
//此处一般需要给数组最后添加结束标志符，具体下面例题会有详细讲解
for (遍历这个数组)
{
	if (栈空 || 栈顶元素大于等于当前比较元素)
	{
		入栈;
	}
	else
	{
		while (栈不为空 && 栈顶元素小于当前元素)
		{
			栈顶元素出栈;
			更新结果;
		}
		当前数据入栈;
	}
}

单调栈的应用我们直接拿一些具体的题来对照应用：

描叙：有n个人站队，所有的人全部向右看，个子高的可以看到个子低的发型，给出每个人的身高，问所有人能看到其他人发现总和是多少。
输入：4 3 7 1
输出：2
解释：个子为4的可以看到个子为3的发型，个子为7可以看到个子为1的身高，所以1+1=2
思路：观察题之后，我们发现实际上题目转化为找当前数字向右查找的第一个大于他的数字之间有多少个数字，然后将每个          结果累计就是答案，但是这里时间复杂度为O(N^2)，所以我们使用单调栈来解决这个问题。

1.设置一个单调递增的栈（栈内0~n为单调递减）
2.当遇到大于栈顶的元素，开始更新之前不高于当前人所能看到的值

int FieldSum(vector<int>& v)
{
	v.push_back(INT_MAX);/这里可以理解为需要一个无限高的人挡住栈中的人，不然栈中元素最后无法完全出栈
	stack<int> st;
	int sum = 0;
	for (int i = 0; i < (int)v.size(); i++)
	{
		if (st.empty() || v[st.top()] > v[i])/小于栈顶元素入栈
		{
			st.push(i);
		}
		else
		{
			while (!st.empty() && v[st.top()] <= v[i])
			{
				int top = st.top();/取出栈顶元素
				st.pop();
				sum += (i - top - 1);/这里需要多减一个1
			}
			st.push(i);
		}
	}
	cout << sum << endl;
	return sum;
}

描述：给出一组数字，求一区间，使得区间元素和乘以区间最小值最大，结果要求给出这个最大值和区间的左右端点
输入：3 1 6 4 5 2
输出：60
       3 5
解释：将3到5（6+4+5）这段区间相加，将和与区间内最小元素相乘获得最大数字60
思路：使用暴力解法求出所有区间，再求出区间的最小值相乘跟新数据，并不是一种很好的算法，所以经过上面俩题的磨         炼，此时我们应该使用一个单调递减栈

1.设置一个单调递减的栈（栈内0~n为单调递增）
2.当遇到小于栈顶元素的值，我们开始更新数据，因为当前遇到的值一定是当前序列最小的

void GetMaxSequence(vector<int>& v)
{
	stack<int> st;
	vector<int> vs(v.size()+1);
	vs[0] = 0;
	for (int i = 1; i < vs.size(); i++)
	{
			vs[i] = vs[i - 1] + v[i-1];
	}
	v.push_back(-1);
	int top, start, end, ret = 0;
	for (int i = 0; i < v.size(); i++)
	{
		if (st.empty() || v[st.top()] <= v[i])
		{
			st.push(i);
		}
		else
		{
			while (!st.empty() && v[st.top()] > v[i])
			{
				top = st.top();
				st.pop();
				int tmp = vs[i] - vs[top];
				tmp = tmp * v[top];
				if (tmp > ret)
				{
					ret = tmp;
					start = top+1;
					end = i;
				}
			}
			st.push(top);
			v[top] = v[i];/与第二题相同的道理，将当前数据的更改最左的top下标，防止出现比当前数据更小的数据
			//这句在这道题里真的超级难理解，但是只要你有耐心相信你可以理解的
		}
	}
	cout << ret << endl;
	cout << start << " "<<end << endl;
}

单调栈是帮助我们完成算法的一个数据结构，很多的题中还是单调栈的身影，更多需要单调栈的题就希望读者自己去发现啦，文章如果有什么问题或者建议希望广大读者们可以提出。