求出数组中每个数下标之后的比该数大的最小数与该数下标之差

Question

给一个数组arr，求出数组中每个数下标之后的比该数大的最小数与该数下标之差，
比如数组: 2 1 4 6 5 3
arr[0]=2与比其大的数中最小数arr[5]=3的坐标之差为5,arr[1]=1与比其大的数中最小数arr[5]=3的坐标之差为4，arr[2]=4与比其大的数中最小数arr[4]=5的坐标之差为2,如果下标之后的数没有比该数大的数，则输出-1，以此类推，最终输出数组为: 5 4 2 -1 -1 -1
给出代码 要求时间复杂度不超过O(n)

Answer 1

该回答引用自GPT-3.5,由博主GISer Liu编写：

首先，我们可以使用单调栈的思想来解决这个问题，具体步骤如下：

1. 创建一个单调递减栈 stack，用于存储数组元素的索引。
2. 遍历数组，对于每个元素：

• 如果栈为空或当前元素小于等于栈顶元素指向的值，将当前元素的索引入栈。
• 否则，循环弹出栈顶元素，直到栈为空或当前元素小于等于栈顶元素指向的值，并记录每个被弹出元素的下一个比它大的数的索引为当前元素的索引。然后将当前元素的索引入栈。

1. 遍历结束后，如果栈中还有元素，表示这些元素后面没有比它们大的数，对应位置的结果为 -1。
   下面是使用 Python 实现的代码：
   python
   Copy code

   def find_next_larger(arr):
   stack = []  # 单调递减栈，存储数组元素的索引
   result = [-1] * len(arr)  # 存储结果，初始值为 -1
   for i in range(len(arr)):
   while stack and arr[i] > arr[stack[-1]]:
   idx = stack.pop()
   result[idx] = i - idx
   stack.append(i)
   return result
   # 测试示例
   arr = [2, 1, 4, 6, 5, 3]
   result = find_next_larger(arr)
   print(result)  # 输出：[5, 4, 2, -1, -1, -1]
   

   这个算法的时间复杂度是 O(n)，因为每个元素最多入栈和出栈一次，且每次入栈和出栈的时间复杂度为 O(1)。

如果该回答解决了您的问题，请采纳！如果没有，请私信联系或评论您的疑惑