Decrease Elements To Make Array Zigzag: Giảm Phần Tử Để Tạo Mảng Zigzag

Đề bài: Cho mảng nums. Mỗi move giảm 1 phần tử bất kỳ đi 1. Mảng zigzag thỏa mãn 1 trong 2 điều kiện:

Even-indexed peaks: A[0] > A[1] < A[2] > A[3] < ...
Odd-indexed peaks: A[0] < A[1] > A[2] < A[3] > ...

Tìm số move tối thiểu.

Ý tưởng

Thử 2 pattern: peak tại index chẵn (bắt đầu 0) và peak tại index lẻ (bắt đầu 1). Với mỗi pattern, duyệt các vị trí peak, giảm nó xuống min(left, right) - 1 nếu cần. Tổng move = sum các lượng giảm.

Code Python


class Solution:
    def movesToMakeZigzag(self, nums: list[int]) -> int:
        def cost(start: int) -> int:
            moves = 0
            for i in range(start, len(nums), 2):
                left = nums[i-1] if i > 0 else float('inf')
                right = nums[i+1] if i+1 < len(nums) else float('inf')
                target = min(left, right) - 1
                if nums[i] > target:
                    moves += nums[i] - target
            return moves
        
        return min(cost(0), cost(1))

# Test
ob = Solution()
print(ob.movesToMakeZigzag([1,2,3]))        # 2
print(ob.movesToMakeZigzag([9,6,1,6,2]))    # 4
print(ob.movesToMakeZigzag([2,7,10,9,8,9])) # 4

Giải thích test case 1: `[1,2,3]`

Pattern 0 (peak at 0,2): i=0 → left=inf, right=2 → target=1, nums[0]=1 OK. i=2 → left=2, right=inf → target=1, nums[2]=3 → giảm 2. Total=2.
Pattern 1 (peak at 1): i=1 → left=1, right=3 → target=0, nums[1]=2 → giảm 2. Total=2.
Min = 2.

Phân tích

Time: O(n)
Space: O(1)
Chỉ cần giảm, không tăng → luôn khả thi.

Kết luận