Find Peak Element
Mảng nums tăng rồi giảm: mỗi giá trị lớn hơn giá trị đứng trước nó cho đến một chỉ số nào đó, và mỗi giá trị sau chỉ số đó nhỏ hơn giá trị đứng trước nó. Một trong hai phần có thể rỗng, vì vậy mảng có thể chỉ tăng hoặc chỉ giảm. Giá trị tại chỉ số chuyển hướng là đỉnh, giá trị duy nhất lớn hơn mọi giá trị lân cận.
Trả về chỉ số của đỉnh trong thời gian O(log n).
Hàm
- numsinteger-array
- các giá trị tăng lên đến một đỉnh rồi giảm xuống
- Trả vềinteger
- chỉ số của đỉnh
Ràng buộc
1 ≤ nums.length ≤ 5000-106 ≤ nums[i] ≤ 106nums[i] != nums[i+1]với mọiihợp lệ.numstăng nghiêm ngặt đến một chỉ số rồi giảm nghiêm ngặt sau đó, nên chỉ có đúng một đỉnh.
Ví dụ
- Đầu vào
- nums = [2, 5, 9, 4, 1]
- Đầu ra
- 2
- Giải thích
- Các giá trị tăng dần qua 2, 5 và 9, sau đó giảm dần qua 4 và 1. Điểm chuyển hướng là 9, chỉ số 2.
- Đầu vào
- nums = [8, 6, 3, -2]
- Đầu ra
- 0
- Giải thích
- Mảng chỉ giảm xuống, nên phần leo lên trống và đỉnh là giá trị đầu tiên, 8 ở chỉ số 0.
- Đầu vào
- nums = [-7, -3, 0, 12, 40]
- Đầu ra
- 4
- Giải thích
- Mảng chỉ tăng dần, nên đỉnh là giá trị cuối cùng, 40 ở chỉ số 4. Các giá trị âm không làm thay đổi điều gì.
Câu hỏi mở rộng
Trong một lưới mà không có hai ô liền kề nào bằng nhau, đỉnh là ô lớn hơn tối đa bốn ô lân cận. Bạn có thể tìm thấy một ô như vậy mà không cần đọc mọi ô không?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Chọn một chỉ số bất kỳ
midvà xemnums[mid+1]. Hướng của bước đó cho bạn biết đỉnh nằm ở đâu?Một bước tăng chỉ xảy ra trước đỉnh, còn một bước giảm chỉ xảy ra tại đỉnh hoặc sau đỉnh. Vì vậy, chỉ cần một phép so sánh là có thể loại trừ một phía của
mid.Duy trì một khoảng luôn chứa đỉnh. Khi bước lên, chuyển
lođếnmid+1; nếu không, chuyểnhiđếnmid. Dừng lại khi chúng gặp nhau.
Lời giải
Với một đỉnh duy nhất, đỉnh là giá trị lớn nhất, nên duyệt một lượt sẽ tìm được đỉnh trong O(n). Để đạt O(log n), hãy so sánh nums[mid] với nums[mid+1]: độ dốc tại mid cho bạn biết nó nằm ở phía nào của đỉnh, vì vậy mỗi bước có thể loại bỏ một nửa phạm vi.
Đi bộ cho đến khi các giá trị bắt đầu giảm
Ý tưởng
Trước đỉnh, mỗi giá trị đều nhỏ hơn giá trị kế tiếp, còn từ đỉnh trở đi, mỗi giá trị đều lớn hơn giá trị kế tiếp. Vì vậy, đỉnh là chỉ số đầu tiên i thỏa mãn nums[i] > nums[i+1], hoặc là chỉ số cuối cùng nếu mảng chỉ tăng.
Khi đỉnh nằm ở cuối mảng có 5000 giá trị, cách duyệt này thực hiện 4999 phép so sánh, trong khi tìm kiếm nhị phân chỉ cần 13 phép.
Thuật toán
- Với
itừ 0 đếnn-2, so sánhnums[i]vớinums[i+1]. - Tại
iđầu tiên mànums[i]lớn hơn, trả vềi. - Nếu vòng lặp kết thúc mà không có lần giảm nào, trả về
n-1.
def findPeakElement(nums):
for i in range(len(nums) - 1):
if nums[i] > nums[i + 1]:
return i # the first step down starts at the peak
return len(nums) - 1 # never went down: the last value is the peakTìm kiếm nhị phân trên độ dốc
Ý tưởng
Đọc một cặp, nums[mid] và nums[mid+1]. Bước tăng có nghĩa là mảng vẫn đang đi lên, điều này trong mảng này chỉ xảy ra trước đỉnh: đỉnh ở mid+1 hoặc bên phải nó. Bước giảm có nghĩa là bạn đang ở đỉnh hoặc đã đi qua đỉnh: đỉnh ở mid hoặc bên trái nó.
Giữ một phạm vi [lo, hi] luôn chứa đỉnh. Bước tăng chuyển lo đến mid+1. Bước giảm chuyển hi đến mid, giữ lại mid vì nó có thể là đỉnh. Khi lo gặp hi, chỉ số còn lại chính là đỉnh. Làm tròn mid xuống giúp nó nhỏ hơn hi, nên mid+1 luôn tồn tại.
Trong ví dụ đầu tiên, mid = 2 thấy 9 > 4, nên hi = 2; sau đó mid = 1 thấy 5 < 9, nên lo = 2, chính là đỉnh. 5000 giá trị cần tối đa 13 bước.
Thuật toán
- Đặt
lo = 0vàhi = n-1. - Khi
lo < hi, lấymid = lo + (hi - lo) / 2, làm tròn xuống. - Nếu
nums[mid] < nums[mid+1], đặtlo = mid + 1. - Nếu không, đặt
hi = mid. - Trả về
lo.
def findPeakElement(nums):
lo, hi = 0, len(nums) - 1 # the peak is always inside [lo, hi]
while lo < hi:
mid = lo + (hi - lo) // 2 # mid < hi, so mid + 1 is a valid index
if nums[mid] < nums[mid + 1]:
lo = mid + 1 # still climbing: the peak is to the right of mid
else:
hi = mid # going down: the peak is mid or to its left
return lo
Lỗi thường gặp và trường hợp biên
- Đặt
hi = mid - 1khi giảm phạm vi tìm kiếm. Trong[2, 5, 9, 4, 1],midđầu tiên chính là đỉnh, vàhi = 1sẽ loại bỏ nó; kết quả tìm kiếm là 1. - So sánh với
nums[mid-1]khi làm trònmidxuống.midcó thể bằng 0, khi đó không có phần tử bên trái. - Dùng phạm vi nửa mở với
hi = n. Khi đó,midcó thể bằngn-1, vànums[mid+1]sẽ đọc vượt quá cuối mảng, ngay cả khi mảng chỉ có một giá trị. - Quên dịch chỉ số trong Lua và R. Đáp án vẫn là chỉ số bắt đầu từ 0, nên vị trí
iđược trả về dưới dạngi-1.
Câu hỏi thường gặp3
Độ phức tạp thời gian của Find Peak Element là bao nhiêu?
Tìm kiếm nhị phân chạy trong thời gian O(log n) và dùng O(1) bộ nhớ, tối đa 13 bước với 5000 giá trị. Duyệt từ trái sang phải có độ phức tạp O(n), vì có thể phải đọc mọi cặp trước khi tìm thấy vị trí giảm.
Cách tìm kiếm nhị phân còn hoạt động khi có nhiều đỉnh không?
Đúng, miễn là các phần tử liền kề khác nhau và các vị trí nằm ngoài hai đầu được tính là thấp hơn mọi giá trị. Kết quả là một đỉnh, không nhất thiết là đỉnh cao nhất. Sau một bước tăng, các giá trị phải chuyển sang giảm chậm nhất là ở cuối phạm vi, và điểm đổi chiều đầu tiên là một đỉnh, nên phía mà thuật toán tìm kiếm giữ lại luôn có một đỉnh.
Đỉnh có luôn là giá trị lớn nhất không?
Trong bài toán này thì đúng: mảng tăng đến một đỉnh rồi giảm xuống, nên không có phần tử nào khác lớn hơn. Với phiên bản có nhiều đỉnh thì không đúng, vì mọi giá trị lớn hơn cả hai phần tử lân cận đều được tính là một đỉnh. Đó là lý do phép tìm kiếm so sánh các phần tử lân cận thay vì tìm giá trị lớn nhất.
Bài tập tương tự
Các bài tập dùng cùng ý tưởng. Giải hai hoặc ba bài là bạn sẽ nhớ được mẫu này.
def findPeakElement(nums):
# Viết code ở đâyKiểm thử #1
Kiểm thử #2
Kiểm thử #3
Đối số
nums = [2, 5, 9, 4, 1]
Đầu ra mong đợi
2