Python程序查找右侧的循环最大元素

假设我们有一个名为 nums 的数字列表。我们必须找到一个相同长度的新列表，其中索引 i 处的值分配给其右侧的下一个大于 nums[i] 的元素，并在需要时循环回到列表的前面。如果没有大于的数字，则应将其设置为 -1。

因此，如果输入类似于 [4, 5, 1, 3]，则输出将为 [5, -1, 3, 4]

为了解决这个问题，我们将遵循以下步骤：

  • n := a 的大小

  • stack := 一个栈，最初插入 0，res := 一个大小为 n 的列表，并填充 -1

  • 对于范围 0 到 1 中的每个值，执行以下操作

    • 对于从 0 到 n-1 的范围内的每个 i，执行以下操作

    • 当 stack 不为空且 a[栈顶] < a[i] 时，执行以下操作

      • res[栈顶] := a[i]

      • 删除栈中的最后一个元素

    • 在栈的末尾插入 i

  • 返回 res

让我们看看以下实现以获得更好的理解：

示例

 在线演示

class Solution:
   def solve(self, a):
      n = len(a)
      stack, res = [0], [-1] * n
      for _ in range(2):
         for i in range(n):
            while stack and a[stack[-1]] < a[i]:
               res[stack[-1]] = a[i]
               stack.pop()
            stack.append(i)
   return res
ob = Solution()
nums = [4, 5, 1, 3]
print(ob.solve(nums))

输入

[4, 5, 1, 3]

输出

[5, -1, 3, 4]

更新于: 2020年10月5日

119 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告