Python程序：查找最长严格递增然后递减的子列表长度

假设我们有一个名为 nums 的数字列表。我们需要找到最长的子列表的长度，其值严格递增然后递减（最小长度为3）。

例如，如果输入为 nums = [7, 1, 3, 5, 2, 0]，则输出为 5，因为子列表 [2, 4, 6, 3, 1] 是严格递增然后递减的。

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

• i := 0，n := a 的大小，res := -infinity
• 当 i < n - 2 时，执行
  • st := i
  • linc := 0，ldec := 0
  • 当 i < n - 1 且 a[i] < a[i + 1] 时，执行
    • linc := linc + 1
    • i := i + 1
  • 当 i < n - 1 且 a[i] > a[i + 1] 时，执行
    • ldec := ldec + 1
    • i := i + 1
  • 如果 linc > 0 且 ldec > 0，则
    • res := res 和 (i - st + 1) 中的最大值
  • 当 i < n - 1 且 a[i] 等于 a[i + 1] 时，执行
    • i := i + 1
• 如果 res >= 0 则返回 res，否则返回 0

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

示例

实时演示

class Solution:
   def solve(self, a):
      i, n, res = 0, len(a), float("-inf")
      while i < n - 2:
         st = i
         linc, ldec = 0, 0
         while i < n - 1 and a[i] < a[i + 1]:
            linc += 1
            i += 1
         while i < n - 1 and a[i] > a[i + 1]:
            ldec += 1
            i += 1
         if linc > 0 and ldec > 0:
            res = max(res, i - st + 1)
         while i < n - 1 and a[i] == a[i + 1]:
            i += 1
      return res if res >= 0 else 0
ob = Solution()
nums = [8, 2, 4, 6, 3, 1]
print(ob.solve(nums))

输入

[[8, 2, 4, 6, 3, 1]

输出

5

Arnab Chakraborty

更新于： 2020年11月19日

385 次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习