Python程序：将数组划分成不相交的区间

假设我们有一个数组 nums，我们需要将其分成两个不同的子数组，分别称为 left 和 right，使得：

  • left 子数组中的每个元素都小于或等于 right 子数组中的每个元素。

  • left 和 right 子数组都非空。

  • left 子数组具有尽可能小的尺寸。

我们需要找到这种划分后 left 的长度。

因此，如果输入类似于 nums = [5,0,3,8,6]，则输出将为 3，因为 left 数组将为 [5,0,3]，而 right 子数组将为 [8,6]。

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

  • mx := null，temp := null，nmx := null

  • temp2 := 0

  • 对于 nums 中的每个 i，执行以下操作：

    • 如果 mx 等于 null，则：

      • mx := i

      • nmx := i

      • temp := temp2

      • temp2 := temp2 + 1

      • 进入下一个迭代

    • 如果 i>=mx，则：

      • temp2 := temp2 + 1

      • 如果 i>nmx，则：

        • nmx := i

      • 进入下一个迭代

    • 否则：

      • temp := temp2

      • temp2 := temp2 + 1

      • mx := nmx

      • 进入下一个迭代

  • 返回 temp+1

示例

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

def solve(nums):
   mx = None
   temp = None
   nmx = None
   temp2 = 0

   for i in nums:

      if(mx==None):
         mx = i
         nmx = i
         temp = temp2
         temp2+=1
         continue

      if(i>=mx):
         temp2+=1
         if(i>nmx):
            nmx = i
         continue

      else:
         temp = temp2
         temp2+=1
         mx = nmx
         continue

   return temp+1

nums = [5,0,3,8,6]
print(solve(nums))

输入

[5,0,3,8,6]

输出

3

更新于：2021年10月7日

220 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告