拓展题 右侧第一个更大元素

Background

  单调栈是一种特殊的栈数据结构，栈中的元素按照某种单调性（递增或递减）排列。它是解决"下一个更大元素"类问题的经典工具，广泛应用于各种算法竞赛和实际项目中。

  通过这个问题，学生将掌握单调栈的核心思想，理解如何利用栈的性质来优化暴力算法，并深入分析时间复杂度的优化过程。

Description

  给定一个由 $N$ 个正整数组成的数组 $a$，对于数组中的每个位置 $i$，请找到它右侧第一个严格大于 $a_i$ 的元素的位置。如果不存在这样的元素，则输出 $-1$。

  要求使用单调栈算法，时间复杂度必须为 $O(N)$。

输入格式

  第一行为一个正整数 $N$（$1 \leq N \leq 10^5$），表示数组的长度。

  第二行包含 $N$ 个空格分隔的正整数 $a_i$（$1 \leq a_i \leq 10^9$），表示数组元素。

输出格式

  输出一行，包含 $N$ 个空格分隔的整数，第 $i$ 个整数表示位置 $i$（从0开始计数）右侧第一个更大元素的位置，如果不存在则输出 $-1$。

样例 #1

样例输入 #1

6
2 1 2 4 3 1

样例输出 #1

3 2 3 -1 -1 -1

样例解释 #1

• 位置0 (值为2)：右侧第一个更大的是位置3 (值为4)
• 位置1 (值为1)：右侧第一个更大的是位置2 (值为2)
• 位置2 (值为2)：右侧第一个更大的是位置3 (值为4)
• 位置3 (值为4)：右侧没有更大的元素
• 位置4 (值为3)：右侧没有更大的元素
• 位置5 (值为1)：右侧没有更大的元素

样例 #2

样例输入 #2

4
1 3 2 4

样例输出 #2

1 3 3 -1

样例解释 #2

• 位置0 (值为1)：右侧第一个更大的是位置1 (值为3)
• 位置1 (值为3)：右侧第一个更大的是位置3 (值为4)
• 位置2 (值为2)：右侧第一个更大的是位置3 (值为4)
• 位置3 (值为4)：右侧没有更大的元素

样例 #3

样例输入 #3

5
5 4 3 2 1

样例输出 #3

-1 -1 -1 -1 -1

样例解释 #3

单调递减数组，每个元素右侧都没有更大的元素。

算法要求

1. 时间复杂度：必须为 $O(N)$，不能使用 $O(N^2)$ 的暴力算法
2. 空间复杂度：额外空间复杂度为 $O(N)$
3. 算法类型：必须使用单调栈算法

扩展思考

1. 如何修改算法来找到左侧第一个更大元素？
2. 如何修改算法来找到右侧第一个更小元素？
3. 能否将算法扩展到处理二维数组？