สมมติว่าเรามีจำนวนอาร์เรย์ เราต้องแบ่งมันออกเป็นสองอาร์เรย์ย่อยที่แตกต่างกันเรียกว่าซ้ายและขวาเพื่อให้ -
-
แต่ละองค์ประกอบในอาร์เรย์ย่อยด้านซ้ายจะน้อยกว่าหรือเท่ากับแต่ละองค์ประกอบในอาร์เรย์ย่อยด้านขวา
-
อาร์เรย์ย่อยด้านซ้ายและขวาไม่ว่างเปล่า
-
อาร์เรย์ย่อยด้านซ้ายมีขนาดเล็กที่สุด
เราต้องหาความยาวของด้านซ้ายหลังจากการแบ่งพาร์ทิชันดังกล่าว
ดังนั้น หากอินพุตเป็น nums =[5,0,3,8,6] เอาต์พุตจะเป็น 3 เพราะอาร์เรย์ด้านซ้ายจะเป็น [5,0,3] และอาร์เรย์ย่อยด้านขวาจะเป็น [8,6]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
mx :=null, temp :=null, nmx :=null
-
temp2 :=0
-
สำหรับแต่ละ i ใน nums ทำ
-
ถ้า mx เหมือนกับ null แล้ว
-
mx :=ผม
-
nmx :=ผม
-
อุณหภูมิ :=temp2
-
temp2 :=temp2 + 1
-
ไปทำซ้ำต่อไป
-
-
ถ้า i>=mx แล้ว
-
temp2 :=temp2 + 1
-
ถ้า i>nmx แล้ว
-
nmx :=ผม
-
-
ไปทำซ้ำต่อไป
-
-
มิฉะนั้น
-
อุณหภูมิ :=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
