อาร์เรย์ที่ไม่ลดลงใน Python

ภาพรวมปัญหา

ให้อาร์เรย์ของจำนวนเต็ม n ตัว เราต้องตรวจสอบว่าอาร์เรย์นี้สามารถกลายเป็นอาร์เรย์ที่ไม่ลดลง (non-decreasing) ได้หรือไม่ โดยการแก้ไขค่าสมาชิกสูงสุด 1 ตัว อาร์เรย์ถือว่าไม่ลดลงเมื่อ array[i] <= array[i + 1] สำหรับทุก i (1 <= i < n)

ตัวอย่าง: อาร์เรย์ [4,2,3] สามารถทำให้เป็น non-decreasing ได้โดยเปลี่ยน 4 เป็น 1 จะได้ [1,2,3]

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

1. ถ้าอาร์เรย์มีสมาชิก 2 ตัวหรือน้อยกว่า ให้คืนค่า True
2. กำหนดตัวแปร ans = False เพื่อติดตามว่าเคยแก้ไขไปแล้วหรือยัง
3. วนลูปจาก index 0 ถึง n-2:
   • ถ้า arr[i] > arr[i + 1] (พบลำดับที่ลดลง):
     • ถ้า ans เป็น True แล้ว (แก้ไขไปก่อนหน้านี้) ให้คืนค่า False
     • ตั้งค่า ans = True
     • ถ้า i > 0 และ arr[i - 1] > arr[i + 1] ให้ปรับ arr[i + 1] = arr[i]
4. คืนค่า True

ตัวอย่างโค้ด (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]))

อินพุต

[4,2,3,5]

เอาต์พุต

True