给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1 。 输入格式 第一行包含整数 N ，表示数列长度。 第二行包含 N 个整数，表示整数数列。 输出格式 共一行，包含 N 个整数，其中第 i 个数表示第 i 个数的左边第一个比它小的数，如果不存在则输出 −1 。 数据范围 1≤N≤105 1≤数列中元素≤109 用c语言写出代码

<think>题目要求：对于数组中的每个元素，找到它左边第一个比它小的数，如果不存在则输出-1。 数据范围：N最大为10^5，因此不能使用O(n^2)的暴力解法，否则会超时。 我们可以使用单调栈来解决这个问题。单调栈的思想是维护一个栈，栈中的元素是单调递增的。 具体步骤： 1. 读取数组长度n和数组a。 2. 创建一个栈（这里用数组模拟栈），一个存储结果的数组res。 3. 遍历数组中的每个元素a[i]（从0到n-1）： while (栈不为空 且 栈顶元素 >= 当前元素a[i]) 弹出栈顶元素（因为栈顶元素比当前元素大或相等，那么它不可能是后续元素的左边第一个比它小的数，因为当前元素更小且更靠右） 此时，如果栈为空，则说明当前元素左边没有比它小的数，输出-1。 否则，栈顶元素就是当前元素左边第一个比它小的数，输出栈顶元素。 然后将当前元素的下标（或者值）入栈。 注意：题目要求输出每个数左边第一个比它小的数，我们可以在栈中存储元素的下标（这样可以直接获取到元素值，同时也可以知道位置关系），也可以存储元素值。但存储下标更方便处理。 具体代码步骤： 1. 定义数组a[100010]存储输入，定义栈stk[100010]（存储下标），定义结果数组res[100010]（可选，也可以直接输出）。 2. 初始化栈顶指针tt=0（这里我们使用数组模拟栈，tt指向栈顶元素的下一个位置，初始为0表示栈空；或者tt=-1表示栈顶位置，这里我习惯用tt表示栈顶指针，初始tt=-1）。 3. 遍历i从0到n-1： while (tt >= 0 && a[stk[tt]] >= a[i]) tt--; // 弹出栈顶直到栈为空或者栈顶元素小于当前元素 if (tt < 0) res[i] = -1; // 栈空，没有比a[i]小的元素 else res[i] = a[stk[tt]]; // 栈顶元素就是第一个比a[i]小的元素 stk[++tt] = i; // 将当前下标入栈 但是注意：题目要求的是左边第一个比它小的数，我们这样维护的栈是单调递增的（从栈底到栈顶递增）。因为当遇到一个较小的数时，会弹出栈中比它大的数，这样栈中每个元素的下一个元素就是左边第一个比它小的数？实际上，我们每次比较的是栈顶元素和当前元素，保证栈是递增的，那么对于当前元素，栈顶就是左边第一个比它小的数。 注意：栈中存储的是下标，通过下标可以访问元素值。 另一种写法（更常见的写法）： int stk[N], tt = -1; // 初始化栈顶指针为-1 for (int i = 0; i < n; i++) { while (tt >= 0 && a[stk[tt]] >= a[i]) tt--; // 出栈 if (tt >= 0) printf("%d ", a[stk[tt]]); else printf("-1 "); stk[++tt] = i; } 但是注意：题目要求输出的是每个数左边第一个比它小的数，并且是输出在一行中，每个数用空格隔开。 然而，上述代码中我们使用下标访问栈中元素，栈中存储的是下标，所以a[stk[tt]]就是栈顶下标对应的元素值。 但是，我们需要注意数据范围：数列中元素最大10^9，所以用int存储是可以的（10^9在int范围内？int最大约2e9，所以可以）。 另外，栈的大小：最多有10^5个元素，所以栈数组大小至少为100010。 代码实现： 注意：输入输出量较大，使用scanf和printf提高效率。 完整代码：</think>以下是使用C语言实现的解决方案，采用**单调栈**算法高效解决该问题： ```c #include <stdio.h> #define N 100010 int stk[N]; // 单调栈（存储数组下标） int tt = -1; // 栈顶指针（初始化为-1表示空栈） int main() { int n, a[N]; scanf("%d", &n); // 读取输入数组 for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } // 处理每个元素 for (int i = 0; i < n; i++) { // 弹出栈顶所有大于等于当前元素的元素 while (tt >= 0 && a[stk[tt]] >= a[i]) { tt--; } // 输出结果 if (tt >= 0) { printf("%d ", a[stk[tt]]); } else { printf("-1 "); } // 当前元素下标入栈 stk[++tt] = i; } return 0; } ``` ### 算法核心思想： 1. **单调栈维护**： - 栈中存储**数组下标**，保持栈底到栈顶对应元素值**严格递增** - 当新元素`a[i]`到来时，弹出所有`>=a[i]`的栈顶元素 - 操作后栈顶即为左边第一个小于`a[i]`的元素 2. **时间复杂度**： - 每个元素最多入栈1次、出栈1次 - 总操作次数为O(N)，满足10^5数据量要求 3. **空间复杂度**： - 栈空间最大为O(N) - 符合题目约束 ### 关键操作解析： - **`while (tt >= 0 && a[stk[tt]] >= a[i]) tt--;`** - 弹出比当前元素大的栈顶元素（它们不可能是后续元素的解） - **`stk[++tt] = i;`** - 将当前下标压栈，保持栈的单调性 - **输出逻辑**： - 栈非空 → 输出栈顶对应元素值 - 栈空 → 输出-1 ### 示例演示： 输入： ``` 5 3 4 2 7 5 ``` 栈变化过程： ``` i=0: 栈空 → 输出-1，栈[0] i=1: a[1]=4 > a[0]=3 → 输出3，栈[0,1] i=2: a[2]=2 < a[1]=4 → 弹出1,0 → 栈空 → 输出-1，栈[2] i=3: a[3]=7 > a[2]=2 → 输出2，栈[2,3] i=4: a[4]=5 < a[3]=7 → 弹出3 → 输出2，栈[2,4] ``` 输出：`-1 3 -1 2 2`