单调递增/递减栈

单调栈

单调栈分为单调递增栈和单调递减栈

单调递增栈：栈中元素从栈底到栈顶是递增的

单调递减栈：栈中元素从栈底到栈顶是递减的

在这里插入图片描述

应用：求解下一个大于x元素或者是小于x的元素的位置

给一个数组，返回一个大小相同的数组，返回的数组的第i个位置的值应当是，对于原数组中的第i个元素，至少往右走多少步，才能遇到一个比自己大的元素(如果之后没有比自己大的元素，或者已经是最后一个元素，则在返回数组的对应位置放上-1)
我们可以先求下一个大于x元素的值
在这里插入图片描述

我们发现这个栈一直都是单调的栈
我们根据代码来更好的理解一下

代码如下：

#include<iostream>
#include<stack>
using namespace std;
int num[100] = { 1,3,4,5,2,9,6 };
int res2[100];
stack<int>s;
void nextGreater(int a[], int n)
{for (int i = n - 1; i >= 0; i--){while (!s.empty() && s.top() <= a[i]){s.pop();}res2[i] = s.empty() ? -1 : s.top();s.push(a[i]);}
}int main()
{nextGreater(num, 7);for (int i = 0; i < 7; i++){cout << res2[i] << " ";}return 0;
}

我们再来看最初的问题，我们移动几步可以遇到第一个比自己大的元素
我们来看res2数组，我们能发现什么规律呢？
在这里插入图片描述

代码如下：

#include<iostream>
#include<stack>
using namespace std;
int num[100] = { 1,3,4,5,2,9,6 };
int res[100];
struct p {int no;int data;
};
stack<p>s;
void nextGreater(int a[], int n)
{for (int i = n - 1; i >= 0; i--){while (!s.empty() && s.top().data <= a[i]){s.pop();}res[i] = s.empty() ? -1 : s.top().no-i;p temp;temp.no = i;temp.data = num[i];s.push(temp);}
}int main()
{nextGreater(num, 7);for (int i = 0; i < 7; i++){cout << res[i] << " ";}return 0;
}