GFG41 Nearest smaller tower

最近较小的塔

给定一个数组，其中每个元素（arr[i]）代表位置 i 处的塔的高度。对于每个 i，我们需要找到最近的索引 j（j > i 或 j < i），其高度小于当前塔的高度（arr[j] < arr[i]）。如果存在两个这样的塔，一个在右边，一个在左边，距离相同，则选择较小的一个，但如果这两个塔的高度相同，则选择索引较小的塔。

示例 1：

输入：1 3 2

输出：-1 0 0

解释：

位置 0 的塔的左侧或右侧没有较小的塔。位置 0 的塔是位置 1 的塔和位置 2 的塔最近的较小的塔。因此输出为 -1 0 0。

示例 2：

输入：4 8 6 5 3

输出：4 0 3 4 -1

您的任务：

您不需要读取输入或打印任何内容。您的任务是完成函数 nearestSmallerTower()，该函数以塔的高度数组作为输入参数，并返回最近较小塔的索引数组。如果两侧都没有较小的塔，则为该塔返回 -1。

预期时间复杂度：O(N)

预期辅助空间：O(N)

约束：

1 <= N <= 105

---------

用stack保存最近的塔，如果大于，那么出栈，同样右边的也是相同的办法处理，然后每个位置左右的塔都找到了，（用两个数组保存）。这样比较两个数组对应值的大小即可，这时候分类讨论就行。

之前abc出过类似的题目，当时没做出来，也没看懂题解，至少现在懂题解了，而且能写出来了。