ภาพรวม
Peak element คือ element ที่มีค่ามากกว่าหรือเท่ากับเพื่อนบ้านทั้งสองข้าง ฟังก์ชันนี้คืน index ของ peak แรกที่เจอ (ไม่ได้หาทุก peak)
ตัวอย่างโค้ด
def find_peak(my_array, array_length):
if array_length == 1:
return 0
if my_array[0] >= my_array[1]:
return 0
if my_array[array_length - 1] >= my_array[array_length - 2]:
return array_length - 1
for i in range(1, array_length - 1):
if my_array[i] >= my_array[i - 1] and my_array[i] >= my_array[i + 1]:
return i
my_list = [1, 3, 20, 4, 1, 0]
list_length = len(my_list)
print("The list is:", my_list)
print("The result is:", find_peak(my_list, list_length))
ผลลัพธ์
The list is: [1, 3, 20, 4, 1, 0]
The result is: 2
คำอธิบาย
- Index 2 มีค่า 20 ซึ่งมากกว่า 3 (ซ้าย) และ 4 (ขวา) -> เป็น peak
- อัลกอริทึมนี้หา peak แรกเจอแล้วคืนค่าทันที (O(n))
- มี peak ได้หลายตัวใน array เดียวกัน
หมายเหตุเกี่ยวกับชื่อ "Alternate Peak"
ชื่อในตัวอย่างอาจสับสน – โค้ดนี้หา peak element ทั่วไป ไม่ใช่ "alternate peak" หากต้องการหา peak สลับกัน (ทีละตัว) ต้องแก้ logic
เวอร์ชันหา Peak ทั้งหมด
def find_all_peaks(arr):
peaks = []
n = len(arr)
if n == 1:
return [0]
if arr[0] >= arr[1]:
peaks.append(0)
for i in range(1, n - 1):
if arr[i] >= arr[i - 1] and arr[i] >= arr[i + 1]:
peaks.append(i)
if arr[-1] >= arr[-2]:
peaks.append(n - 1)
return peaks
print(find_all_peaks([1, 3, 20, 4, 1, 0])) # [2]
print(find_all_peaks([1, 3, 2, 4, 1])) # [1, 3]
