单调栈结构

单调栈结构可以得到一个数组中某位置左侧右侧比该位置元素大的元素和对应的索引值；
比如数组Arr = [5,4,6,7,2]
位置2对应的元素6；左侧比他大的元素是None，右侧比它大的元素为7；

应用1

1. 当数组中没有重复元素的时候，返回数组中每一个位置左右两侧第一个大于该位置元素的元素值，如果某一侧没有满足条件的元素，就返回-1

• 思路
  维护一个栈底到栈顶元素绝对递减的栈，依次遍历输入元素，当满足递减栈条件的时候，将元素压入栈；但是如果遍历的元素不满足单调栈的条件，这个时候就产生了结果，此时位于栈顶的元素索引位置的左右侧首个大于的元素就可以得到；加入此时栈顶的元素索引为k，那么R_res[k]=此时遍历到的待压入栈的元素；L_res[k]=栈中元素k底下的元素
• code

#include<iostream>
#include<list>
#include<vector>
#include <stack>
using namespace std;

int main()
{
    
	stack<int> st;
	vector<int> R_res;
	vector<int> L_res;
	vector<int> in_vec = {
     3,6,4,2,8,9};
	R_res.resize(in_vec.size());
	L_res.resize(in_vec.size());

	for (int i = 0; i < in_vec.size(); i++)
	{
    
		while(!st.empty() && in_vec[st.top()] < in_vec[i])
		{
    
			int idx = st.top();
			R_res[idx] = in_vec[i];
			st.pop();
			if (!st.empty())
				L_res[idx] = in_vec[st.top()];
			else
				L_res[idx] = -1;
		}
		st.push(i);
	}
	
	int tail = -1;
	while (!st.empty())
	{
    
		int idx = st.top();
		R_res[idx] = tail;
		st.pop();
		if (!st.empty())
			L_res[idx] = in_vec[st.top()];
		else
			L_res[idx] = -1;
	}
	for (int i = 0; i < R_res.size(); i++)
	{
    
		cout << L_res[i] << " " << R_res[i] << endl;
	}
	return 0;
}

#output
-1 6
-1 8
6 8
4 8
-1 9
-1 -1

应用2

当数组中有重复元素的时候，返回数组中每一个位置左右两侧第一个大于该位置元素的元素值

• 思路
  同样的也是维护一个单调栈，只不过栈元素为链表的地址，把相同元素对应的索引放进一个有序表或者无序表里边；

• code

stack<vector<int>> st;

待续
视频：两小时30分处

应用3

数组中假设累计和与最小值的乘积，假设叫做数组的指标A；那么给定一个数，请返回子数组中指标A最大的值；

给定数组Arr = [5,3,2,1,6,4,7,8],返回子数组中的最大指标A；

• 思路
  这个数组没有重复值，比较简单，可以使用单调栈在没有重复元素时候的解法；数组的所有的子数组构成的集合可以分为8个小集合；既分别是以每个元素为最小值构成的子数组集合；所以题目就变成了分别以数组中每个元素为最小值的子数组中，指标A最大；对于最小值相同的子数组集合，元素累计和最大的子数组对应指标A最大的子数组；
  所以问题简化为，求每个元素左右两侧小于该元素的元素索引，那么左右两个索引之内的元素就是该元素产成指标A最大的子数组；这就用到了最大栈；
  维护一个栈底到栈顶元素递增的栈

• code

#include<iostream>
#include<list>
#include<vector>
#include <stack>
using namespace std;

int main()
{
    
	stack<int> st;
	vector<int> R_res;
	vector<int> L_res;
	int M = INT_MIN;
	vector<int> M_Arr;
	vector<int> in_vec = {
     3,6,4,2,8,9};
	R_res.resize(in_vec.size());//记录索引
	L_res.resize(in_vec.size());//记录索引

	for (int i = 0; i < in_vec.size(); i++)
	{
    
		while(!st.empty() && in_vec[st.top()] > in_vec[i])
		{
    
			int idx = st.top();
			R_res[idx] = i;
			st.pop();
			if (!st.empty())
				L_res[idx] = st.top();
			else
				L_res[idx] = -1;
		}
		st.push(i);
	}
	
	int tail = in_vec.size();
	while (!st.empty())
	{
    
		int idx = st.top();
		R_res[idx] = tail;
		st.pop();
		if (!st.empty())
			L_res[idx] = st.top();
		else
			L_res[idx] = -1;
	}
	for (int i = 0; i < R_res.size(); i++)
	{
    
		cout << L_res[i] << " " << R_res[i] << endl;
	}

	for (int i = 0; i < R_res.size(); i++)
	{
    
		int idx1 = L_res[i];
		int idx2 = R_res[i];
		int sum = 0;
		int res ;
		for (int k = idx1 + 1; k < idx2; k++)
			sum += in_vec[k];
		res = in_vec[i] * sum;
		M_Arr.push_back(res);
		M = max(M, res);
	}
	cout << "the max A is:" << M << endl;
	for (int i = 0; i < R_res.size(); i++)
		cout << M_Arr[i] << " ";
	return 0;
}

#output
-1 3
0 2
0 3
-1 6
3 6
4 6
the max A is:136
39 36 40 64 136 81