题目提示要用归并排序,易得本蒟蒻根本不会qwq,但是整了一个猎奇的单调栈解法qwq
时间复杂度:O(n)O(n)O(n)
思路
维护一个单调栈,优化时间复杂度。
遍历目标数组,维护一个单调栈:
1. 循环
1. 栈不为空,且栈顶元素小于x:出栈,待下一轮查看栈顶元素是否满足要求。(继续循环)
2. 不满足 1 的条件:结束循环。
2. 循环结束。
1. 栈不为空:找到了第一个满足条件的元素,输出栈顶元素。
2. 栈为空:没有满足要求的元素,输出-1.
3. 将x入栈:要么栈顶元素小于x,要么栈为空,两种情况都可以继续维护单调栈。
代码