Chương trình Python tìm chỉ số đỉnh cục bộ (local peaks) trong danh sách

Cho danh sách nums. Tìm chỉ số mọi đỉnh cục bộ (peak), coi các plateau (dãy giá trị bằng nhau) là đỉnh nếu thỏa mãn:

1. Giá trị bên phải khác đầu tiên (nếu có) nhỏ hơn.
2. Giá trị bên trái khác đầu tiên (nếu có) nhỏ hơn.
3. Có ít nhất 1 giá trị khác ở trái hoặc phải.

Ví dụ

nums = [5, 8, 8, 8, 6, 11, 11]
Output: [1, 2, 3, 5, 6]
Giải thích: Plateau 8 tại index 1,2,3 là đỉnh (5<8>6). Plateau 11 tại 5,6 là đỉnh (6<11, hết phải).

Thuật toán: Quét plateau

1. Duyệt i từ 0 đến n-1, nhóm các giá trị liên tiếp bằng nhau thành plateau [i0, i).
2. Kiểm tra plateau [i0, i-1] có phải đỉnh không: - Trái: i0==0 HOẶC nums[i0] > nums[i0-1] - Phải: i==n HOẶC nums[i0] > nums[i] - Không phải bằng phẳng toàn mảng: i0!=0 HOẶC i!=n
3. Nếu thỏa → thêm tất cả index trong plateau vào kết quả.

Code Python

def solve(nums):
    n = len(nums)
    ans = []
    i = 0
    while i < n:
        i0 = i
        # Nhóm plateau
        while i < n and nums[i] == nums[i0]:
            i += 1
        # Kiểm tra đỉnh
        left_ok = (i0 == 0) or (nums[i0] > nums[i0 - 1])
        right_ok = (i == n) or (nums[i0] > nums[i])
        not_flat = (i0 != 0) or (i != n)
        if left_ok and right_ok and not_flat:
            ans.extend(range(i0, i))
    return ans

# Test
print(solve([5, 8, 8, 8, 6, 11, 11]))  # [1, 2, 3, 5, 6]
print(solve([1, 2, 3, 4]))              # [3]
print(solve([4, 3, 2, 1]))              # [0]
print(solve([2, 2, 2]))                 # [] (bằng phẳng toàn mảng)

Giải thích plateau [8,8,8] tại index 1,2,3

• i0=1, i=4 (dừng tại nums[4]=6 != 8).
• Trái: nums[1]=8 > nums[0]=5 ✓
• Phải: nums[1]=8 > nums[4]=6 ✓
• Khác phẳng: i0=1≠0 ✓
• → Thêm 1,2,3.

Độ phức tạp

• Thời gian: O(n) - mỗi phần tử thăm 1 lần.
• Không gian: O(p) (p = số đỉnh, output).