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 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告