题目描述

找出1个数左边第一个比它小的数

样例

blablabla

算法1 :暴力枚举

时间复杂度

$O(n^2)$

算法2：单调栈

通过维护单调栈的数据结构–维护1个从栈底到栈顶，数据单调上升的栈的数据结构。
每次更新的栈顶为结果
关于单调栈的维护：只在push stack部分多加了一个判断单调与否的条件，其他栈操作相同。

blablabla

时间复杂度

第一个循环，O(n)的复杂度；当出现栈顶元素 >= 读入元素时，需要维护栈的单调性的时候，会删除。
由于最差情况，将读入的都删除一遍（且一个元素删除后不会再重复读入），复杂度为O(n)。因此，整体时间复杂度还是O(n)

C++ 代码

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int stk[N], index = -1;

int main() {
    int M;
    cin >> M;
    for (int i = 0; i < M; i++) {
        int num;
        cin >> num;
        if (i == 0) {
            cout << -1 << ' ';
            stk[++index] = num;
        }
        else {
            while (index >= 0 && stk[index] >= num) { // 即使为while (stk[index] >= num) 也ac，可编译通过也不报错，C++数组越界机制很神奇：test case 2 1
                index--; //del(栈顶元素);
            }
            if (index >= 0) { //如果栈不为空
                cout << stk[index] << ' ';
                stk[++index] = num;
            }
            else {
                cout << -1 << ' ';
                stk[++index] = num;
            }
        }   
    }
    return 0;
}