Mảng Không Giảm trong Python

Cho một mảng gồm n số nguyên, nhiệm vụ là kiểm tra xem mảng có thể trở thành mảng không giảm (non-decreasing) bằng cách sửa đổi tối đa một phần tử hay không. Mảng được gọi là không giảm nếu thỏa mãn điều kiện: array[i] <= array[i + 1] với mọi i (1 <= i < n). Ví dụ, mảng [4,2,3] sẽ trả về true vì ta có thể đổi 4 thành 1 để được mảng [1,2,3].

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

1. Nếu mảng có 2 phần tử trở xuống, trả về true.
2. Khởi tạo biến ans = False để đánh dấu đã sửa đổi chưa.
3. Duyệt qua mảng từ chỉ số 0 đến len(arr) - 2:
   • Nếu arr[i] > arr[i + 1] (vi phạm điều kiện không giảm):
     • Nếu ans đã là True (đã sửa trước đó), trả về false.
     • Ngược lại, đặt ans = True.
     • Nếu i > 0 và arr[i - 1] > arr[i + 1], gán arr[i + 1] = arr[i] để khắc phục vi phạm.
4. Trả về true.

Ví dụ (Python)

class Solution(object):
    def checkPossibility(self, nums):
        if len(nums) <= 2:
            return True
        ans = False
        for i in range(len(nums) - 1):
            if nums[i] > nums[i + 1]:
                if ans:
                    return False
                else:
                    ans = True
                if i > 0:
                    if nums[i - 1] > nums[i + 1]:
                        nums[i + 1] = nums[i]
        return True

ob1 = Solution()
print(ob1.checkPossibility([4, 2, 3, 5]))

Đầu vào

[4, 2, 3, 5]

Đầu ra

True