โปรแกรมหาจำนวนการดำเนินการน้อยที่สุดเพื่อทำให้อาร์เรย์เพิ่มขึ้นอย่างเคร่งครัดด้วย Python

สมมติว่าเรามีอาร์เรย์ nums ในหนึ่งการดำเนินการ เราสามารถเลือกอิลิเมนต์หนึ่งและเพิ่มค่าขึ้น 1 เช่น [4,5,6] เลือก index 1 ได้ [4,5,5] ต้องการหาจำนวนการดำเนินการน้อยที่สุดเพื่อทำให้ nums เพิ่มขึ้นอย่างเคร่งครัด (strictly increasing)

เช่น nums = [8,5,7] ผลลัพธ์คือ 7 เพราะต้องเพิ่มเป็น [8,6,7]→[8,7,7]→[8,8,7]→[8,9,7]→[8,9,8]→[8,9,9]→[8,9,10]

ขั้นตอนการแก้ปัญหา

• count = 0
• วนลูป i จาก 0 ถึง len(nums)-2:
  • ถ้า nums[i+1] ≤ nums[i]:
    • count += nums[i] - nums[i+1] + 1
    • nums[i+1] += nums[i] - nums[i+1] + 1 (ทำให้ nums[i+1] = nums[i] + 1)
• คืนค่า count

ตัวอย่างโค้ด

def solve(nums):
    count = 0
    for i in range(len(nums) - 1):
        if nums[i+1] <= nums[i]:
            count += nums[i] - nums[i+1] + 1
            nums[i+1] += nums[i] - nums[i+1] + 1
    return count

nums = [8,5,7]
print(solve(nums))

ข้อมูลเข้า

[8,5,7]

ข้อมูลออก

7