单调栈

前几天写的一道单调栈的模板题，今天补一下笔记

这里放一下题~🚩

首先，看一下数据~
很好1e5，使我朴素做法报废😒
不过既然是模板题肯定不会难，所以简单了解一下本次主角：单调栈
从名字就可以看出，这是一种特殊的栈，栈内元素保持单调性😙

拿第一个测试样例的数据来做演示：a[0] = 77, a[1] = 35, a[2] = 52, a[3] = 10, a[4] = 37.

• 我们先定义一个栈 和一个答案数组 stack<int> idx;，这个栈用来存放当前比较的数字的下标，答案数组ans[i]表示原数组下标为i的数左边第一个比自己小的数的情况。

• 由于是找左边第一个比自己小的数字，所以我们从右边开始循环，栈为空或者当前元素大于等于栈顶值（偷懒叫它栈顶值，表示栈顶下标对应的数），就将它进栈。否则就将当前栈顶元素出栈，当前下标进栈，因为栈顶值左边第一个小于它的数已经找到了，即为遍历到的当前值。
  

  

（第一次循环直接入栈，所以跳过了😉😉） 很明显，当前值小于栈顶值，所以我们把当前值10存到ans[4]表示原数组下标为4的数字的“左一小值”找到了。❤️ 原谅我这样叫，太懒了
然后我们进行循环比较，如果栈不为空并且栈顶值仍小于当前值，那么继续出栈进栈，直到栈空或栈顶值大于当前值。
所以，答案数组变成这样了：

然后我们继续~

到这里我们再看，当前值大于栈顶值，所以把当前下标进栈，继续往前遍历~

当前值又一次小于栈顶值，所以还是循环比较，每次循环中出栈下标对应的数字的“左一小值”都找到了，然后更新答案数组，这里就不贴图片了。再往前走~

哟西，走完了 我们现在遍历到了第一个数字，还是先进行比较，当前值大于栈顶值，进栈，结束循环了。

西卡西！我们栈里面还有三个下标，怎么办呢？那么现在我们再来看一下答案数组~

我们发现答案数组并没有被填满，因为我们进行进栈操作时的条件是当前值大于等于栈顶值，而如果进栈之前栈中还有元素，那表示栈中剩余的元素对应的值到目前为止仍没有“左一小值”。其实也很好理解，当前值因为大于栈顶值，所以才要进栈，而栈顶值又是因为大于前一个“当前值”进栈的，所以当前值肯定也是大于前一个“当前值”的，因此留在栈里的元素对应的值到目前为止都没有“左一小值”，那么等到遍历完还留在栈中的自然就要往答案数组里面填入“-1”（视题目要求而定）。

所以最后一步就是要把剩余的元素依次出栈并把对应的答案数组更新为“-1”.
也就是进行一个循环直到栈空
循环：ans[idx.top()] = -1;，然后idx.pop();

更新完的ans数组：

对比一下，没有问题，再测试一下，完美过了样例。
思路并不难，在纸上写写画画能更好理解

时间复杂度：O(n)

最后贴一下完整代码~

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

stack<int> idx;
int ans[N], a[N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    for (int i = n - 1; i >= 0; i--) {
        if (idx.empty() || a[i] >= a[idx.top()]) {
            idx.push(i);
        }
        else {
            while (!idx.empty() && a[i] < a[idx.top()]) {
                ans[idx.top()] = a[i];
                idx.pop();
            }
            idx.push(i);
        }
    }
    
    while (!idx.empty()) {
        ans[idx.top()] = -1;
        idx.pop();
    }
    
    for (int i = 0; i < n; i++) cout << ans[i] << " ";
    
    return 0;
}

完活，收工~