最近可以是左边或者右边最近的
观察单调队列的逻辑模型，每个黄色元素左侧第一个小于它的元素，是前一个黄色元素，根据入队列过程中，每一个元素都『黄』过，那么将所有元素依次入队，当前元素在队列中的前一个元素，即是问题所求。
这种不从头部出的结构，我们叫他【单调栈】
对于新入栈的元素来说，所有能被他打动的，都是违反了单调性的，就会把这些踢出去了。直到有一个元素我打动不了了，那么将『我』也就是新入栈的元素入栈
所有被我打动的？我是他们的男神
那个我打动不了的，她是我的女神
新入栈的蓝色方块能干掉所有违反单调性的
在单调递减栈的时候，这个单调性是递减--也就是蓝色方块都比黄色方块要大！
🟦是后面第一个比🟨大的！
🟩是前面第一个比🟦大的
总结得出：
单调递减栈可以维护最近的大于关系
『上面就是两个大于关系「参考最后一个🟩和🟦」』
并且当前的🟦不就是将来的🟨么
所以单调递减栈就可以找出当前元素左右两侧离他最近的比他大的元素！
也就是『维护最近的大于/小于关系』
它的结构其实和单调队列一样，都是创建一个单调的序列并维护它。 只不过是将队列的尾进头出变成了尾进尾出。
单调队列违反单调性的元素尾出，超过窗口的头出。单调栈不存在窗口，只有违反单调性的尾出。
类似于单调队列的单调性，维护最近最大值就是采用递减栈，因为新进去的元素要弹出所有比他小的元素，直到不能弹出为止。 它左边的就是大于它的最大元素了 口诀：对于递减栈
所有我能打动的，我比他们值更大; 不能打动的，他比我大
所以那个我不能打动的就是第一个比我大的了，也就是最近比我大的！
对于一个序列来说，
void output(vector<int> arr, const char *s) {
printf("%s", s);
for (auto x : arr) {
printf("%5d", x);
}
printf("\n");
return ;
}
int main() {
int n;
cin >> n;
vector<int> ind(n);
vector<int> arr(n);
// pre nex 分别维护元素前面、后面比他小的元素！
// 所以用单增栈
vector<int> pre(n), nex(n);
stack<int> s;
for (int i = 0; i < n; ++i) ind[i] = i;
for (int i = 0; i < n; ++i) cin >> arr[i];
// 每个元素依次压入s
// pre和nex存前边后边比他小的最近元素的下标
// 所以维护递增栈
for (int i = 0; i < n; ++i) {
// 是否违反单调性
while (s.size() && arr[i] < arr[s.top()]) {
// arr[i]是当前是违反单调性的
// 也就是你能打动的所有元素的后边最近的最小值
// 也就是🟦
// 也就是nex记录了若干🟨后面最近的最小
nex[s.top()] = i;
s.pop();
}
// 这里对于s为空的情况处理下
// s为空之后 证明前面没有比他小的了
// 所以设成-1
if (s.size() == 0) pre[i] = -1;
// 那么当前到的i位置即为不能打动的即不违反单调性的位置了
// 也就是🟩 前面最近最小的
// 也就是pre记录了新入栈元素的前面的最小
else pre[i] = s.top();
s.push(i);
}
// 走到这一步说明后面没有比他更小的了
// 那就设成最后一位 也就是-1 n都是边界
while (s.size()) nex[s.top()] = n, s.pop();
output(ind, "ind: ");
output(arr, "now: ");
output(pre, "pre: ");
output(nex, "nex: ");
return 0;
}❯ ./a.out
10 5 7 4 2 1 3 6 8 0 9
ind: 0 1 2 3 4 5 6 7 8 9
now: 5 7 4 2 1 3 6 8 0 9
pre: 1 0 1 1 1 4 5 6 1 8
nex: 2 2 3 4 8 8 8 8 10 10pre nex存的都是下标 这样就可对应的看出来每个位置前面后面最近比他小的元素了
比如3 前面比他小的元素是1 下标为4 后面比他小的是0 下标是8
Leetcode 155 503 901 739