php做网站的好处/上海seo优化外包公司

单调栈的分类

单调递增栈：栈中的元素从栈底到栈顶是单调递增的。不难发现，单调递增栈的出栈序列递减

单调递减栈：栈中的元素从栈底到栈顶是单调递减的。不难发现，单调递减栈的出栈序列递增

单调栈的应用

• 求数列中每个元素X的右边第一个大于元素X的新元素Y
• 求数列中每个元素X的左边第一个小于元素X的新元素Y
• 给一个数组，返回一个大小相同的数组，返回的数组的第i个位置的值是对于原数组中的第i个元素，至少往右走多少步，才能遇到一个比自己大的元素
• 给一个数组，返回一个大小相同的数组，返回的数组的第i个位置的值是对于原数组中的第i个元素，至少往左走多少步，才能遇到一个比自己小的元素
• 如果不存在，则输出-1

实例

上图的数组，对于每一个元素X，求解右边第一个大于X的元素，分别是3、4、5、9、9、-1、-1，保存在另一个数组res1中，如下图：

代码实现：

#include <iostream>
#include <stack>using namespace std;const int N = 1e5 + 10;
int n;//数组长度
int a[N];//存储数据
int res[N];//存储结果//单调栈模板,找到长度为n的a数组中下一个大于X的元素Y
void nextgreaterNum(int a[],int n)
{ stack<int> st;for (int i = n - 1;i >= 0;i--)//从后往前遍历{while (!st.empty() && st.top() <= a[i]) st.pop();res[i] = (st.empty() ? -1 : st.top());st.push(a[i]); }
}int main()
{cin >> n;for (int i = 0;i < n;i++) cin >> a[i];nextgreaterNum(a,n);for (int i = 0;i < n;i++) cout << res[i] << " ";return 0;
}

输入
7
1 3 4 5 2 9 6
输出
3 4 5 9 9 -1 -1

单调栈模板

在长度为n的a数组中找到下一个大于X的元素Y：

void nextgreaterNum(int a[],int n)
{ stack<int> st;for (int i = n - 1;i >= 0;i--)//从后往前遍历{while (!st.empty() && st.top() <= a[i]) st.pop();res[i] = (st.empty() ? -1 : st.top());st.push(a[i]); }
}

那么，如果要从左边找第一个小于元素X的新元素Y，应该如何修改模板？
在长度为n的a数组中找到上一个小于X的元素Y：

void nextgreaterNum(int a[],int n)
{ stack<int> st;for (int i = 0;i < n;i++)//从前往后遍历{while (!st.empty() && st.top() >= a[i]) st.pop();res[i] = (st.empty() ? -1 : st.top());st.push(a[i]); }
}

作业题：Acwing 830 单调栈
提示：直接套用以上模板即可

单调栈进阶

以上例题只需要找出某个元素X左边第一个小于元素X的新元素，或者某个元素X右边第一个大于元素X的新元素。如果题目要求对于数组中的每个元素X，至少向左走多少步，才能遇到一个比它小的元素？或者对于数组中的每个元素X，求出至少向右走多少步，才能遇到一个比它大的元素？应该如何实现呢？(提示：利用结构体)

如，输入五个元素，分别是3、4、2、7、5。3至少走1步，4至少走2步，2至少走1步，7走多少步都遇不到比它大的数，故输出-1，同理，5输出-1。
代码实现：

#include <iostream>
#include <stack>using namespace std;const int N = 1e5 + 10;
int n;//数组长度
int a[N];//存储数据
int res[N];//存储结果struct node
{int pos;//当前元素的位置int data;//当前元素的值
};//单调栈模板,找到长度为n的a数组中下一个大于X的元素Y
void nextgreaterNum(int a[],int n)
{ stack<node> st;for (int i = n - 1;i >= 0;i--)//从后往前遍历{while (!st.empty() && st.top().data <= a[i]) st.pop();res[i] = (st.empty() ? -1 : st.top().pos - i);//将当前点入栈node temp;temp.pos = i;temp.data = a[i];st.push(temp);}
}int main()
{cin >> n;for (int i = 0;i < n;i++) cin >> a[i];nextgreaterNum(a,n);for (int i = 0;i < n;i++) cout << res[i] << " ";return 0;
}

输入
5
3 4 2 7 5
输出
1 2 1 -1 -1