Chương trình tìm số phép toán tối thiểu để mảng tăng chặt bằng Python

Cho mảng nums. Mỗi phép toán tăng một phần tử lên 1. Tìm số phép tối thiểu để mảng trở thành tăng chặt (nums[i] < nums[i+1] ∀i).

Ví dụ: nums = [8,5,7] → cần 7 phép: [8,6,7]→[8,7,7]→[8,8,7]→[8,9,7]→[8,9,8]→[8,9,9]→[8,9,10].

Thuật toán giải quyết

• count := 0.
• Duyệt i từ 0 đến n-2:
  • Nếu nums[i+1] ≤ nums[i]: cần tăng nums[i+1] lên nums[i]+1. Số phép = nums[i] - nums[i+1] + 1. Cộng vào count, cập nhật nums[i+1].
• Trả về count.

Ví dụ triển khai

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))

Đầu vào

[8,5,7]

Đầu ra

7