asp.net+网站开发+实战,局网站建设,做外贸网站怎么做,重庆市建设工程节能中心网站1. 问题描述
给定一个环形数组#xff08;最后一个元素的下一个元素是数组的第一个元素#xff09;#xff0c;为每个元素打印下一个更大的元素。数字x的下一个更大的数#xff0c;是遍历数组的过程中出现的第一个更大的数字#xff0c;这意味着可以循环搜索以查找其下一…1. 问题描述
给定一个环形数组最后一个元素的下一个元素是数组的第一个元素为每个元素打印下一个更大的元素。数字x的下一个更大的数是遍历数组的过程中出现的第一个更大的数字这意味着可以循环搜索以查找其下一个更大的数字如果它不存在则为此数字输出-1。注意给定数组的长度不超过10000。
2. 问题示例
输入[121]输出[2-12]第一个1的下一个更大的数字是2数字2找不到下一个更大的数字第二个1的下一个更大的数字需要循环搜索答案也是2。
3. 代码实现
使用单调栈算法实现。单调栈算法是一种常用的栈操作技巧它通过维护一个单调递减或单调递增的栈来实现一些特定的操作。
def next_greater_element(nums):n len(nums)result [-1] * n # 初始化结果列表为-1stack [] # 使用一个栈来维护单调递减序列# 遍历两倍长度的数组以处理循环的情况for i in range(2 * n):# 对于每个元素不断弹出栈顶元素直到栈顶元素小于当前元素或者栈为空while stack and nums[stack[-1]] nums[i % n]:index stack.pop()result[index] nums[i % n]# 将当前元素的下标压入栈中stack.append(i % n)return result
nums [1, 2, 1]
result next_greater_element(nums)
print(result)
这个算法的时间复杂度是O(n)其中n是数组的长度。
在算法中我们遍历两倍长度的数组并使用一个栈来维护单调递减序列。对于每个元素我们不断弹出栈顶元素直到栈顶元素小于当前元素或者栈为空并将当前元素的下标压入栈中。最后我们得到每个元素的下一个更大的元素。因此整个算法的时间复杂度是O(n)。
