Python程序：查找字典序最大的山脉列表

假设我们有三个正数n、lower和upper。我们需要找到一个长度为n的列表，该列表严格递增，然后严格递减，所有数字都在[lower, upper]（包含两端）范围内。并且递增和递减部分都应该是非空的。我们需要找到可能的字典序最大的列表，如果不可能，则返回空列表。

因此，如果输入类似于n = 5 lower = 3 upper = 7，则输出将是[6, 7, 6, 5, 4]，如果我们仔细观察，[7, 6, 5, 4, 3] 是无效的，因为严格递增的部分应该是非空的。

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

  • 如果 n > 2 * (upper - lower) + 1，则

    • 返回空列表

  • c := upper - lower

  • d := 1

  • 如果 c < n，则

    • d := n - c - 1

  • 如果 d 等于 0，则

    • d := 1

  • f := 从 (upper - d) 到 (upper - 1) 的范围创建一个新列表

  • g := 从 (upper - n + d - 1) 倒序到 upper 的一个新列表

  • 连接 f 和 g 并返回

示例

让我们看看下面的实现以更好地理解

def solve(n, lower, upper):
   if n > 2 * (upper - lower) + 1:
      return []
   c = upper - lower
   d = 1
   if c < n:
      d = n - c - 1
   if d == 0:
      d = 1
   f = list(range(upper - d, upper))
   g = list(range(upper, upper - n + d, -1))
   return f + g

n = 5
lower = 3
upper = 7
print(solve(n, lower, upper))

输入

5, 3, 7

输出

[6, 7, 6, 5, 4]

更新于：2021年10月11日

浏览量：180

开启你的职业生涯

完成课程获得认证

开始学习
广告