Decrease Elements To Make Array Zigzag: ลดค่าให้ Array เป็น Zigzag

โจทย์

กำหนด array nums operation เดียวคือ "ลดค่าลง 1" หาจำนวน operation น้อยที่สุด ทำให้ array กลายเป็น Zigzag:

• Pattern 1 (even peaks): A[0] > A[1] < A[2] > A[3] < A[4] > ...
• Pattern 2 (odd peaks): A[0] < A[1] > A[2] < A[3] > A[4] < ...

ตัวอย่าง: [1,2,3] → 2 operations (ลด 2→0 หรือ 3→1)

ข้อสังเกต

เนื่องจาก operation มีแค่ "ลดค่า" เราไม่สามารถเพิ่มค่าได้ ดังนั้นสำหรับแต่ละตำแหน่งที่ต้องเป็น "peak" (มากกว่าเพื่อนบ้าน) เราต้องลดเพื่อนบ้านให้ต่ำกว่า peak

อัลกอริทึม: ลองทั้ง 2 Pattern

1. สำหรับแต่ละ pattern (เริ่ม peak ที่ index 0 หรือ 1):
2. วนลูปทุก index ที่ต้องเป็น peak
3. หาค่า min ของเพื่อนบ้านซ้ายและขวา
4. ถ้า peak ≤ min_neighbor: ต้องลด peak ให้เหลือ min_neighbor - 1
5. รวม operations ทั้งหมด
6. คำตอบ = min(ops_pattern1, ops_pattern2)

การติดตั้ง (Python Implementation)

class Solution:
    def movesToMakeZigzag(self, nums: list[int]) -> int:
        def calc_ops(start: int) -> int:
            """คำนวณ operations สำหรับ pattern ที่ peak เริ่มที่ start (0 หรือ 1)"""
            ops = 0
            n = len(nums)
            for i in range(start, n, 2):
                left = nums[i-1] if i-1 >= 0 else float('inf')
                right = nums[i+1] if i+1 < n else float('inf')
                min_neighbor = min(left, right)
                if nums[i] >= min_neighbor:
                    ops += nums[i] - (min_neighbor - 1)
            return ops
        
        return min(calc_ops(0), calc_ops(1))

# ทดสอบ
ob = Solution()
print(ob.movesToMakeZigzag([1,2,3]))           # 2
print(ob.movesToMakeZigzag([9,6,1,6,2]))       # 4
print(ob.movesToMakeZigzag([1,2,3,4,5]))       # 4
print(ob.movesToMakeZigzag([2,1,2]))           # 0 (already zigzag)

Output

2
4
4
0

การวิเคราะห์ตัวอย่าง [1,2,3]

Pattern 1 (peak at even: 0,2): 
  i=0: left=inf, right=2, min=2, nums[0]=1 < 2 ✓ (0 ops)
  i=2: left=2, right=inf, min=2, nums[2]=3 ≥ 2 → ต้องลด 3→1 (2 ops)
  Total: 2

Pattern 2 (peak at odd: 1):
  i=1: left=1, right=3, min=1, nums[1]=2 ≥ 1 → ต้องลด 2→0 (2 ops)
  Total: 2

min(2, 2) = 2

Complexity

• Time: O(n) - วนลูป array 2 ครั้ง
• Space: O(1) - ใช้ตัวแปรคงที่

สรุป

โจทย์ Zigzag Array แก้ได้โดยพิจารณา 2 pattern แยกกัน สำหรับแต่ละ peak ให้ลดค่า peak ให้ต่ำกว่าเพื่อนบ้านน้อยที่สุด 1 หน่วย (เพราะ operation แค่ลดค่า) เลือก pattern ที่ใช้ operations น้อยกว่า

หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็นครับ