Chúng ta cần viết một hàm JavaScript nhận vào một mảng số làm đối số đầu tiên và duy nhất.
Hàm nên tìm và trả về một số từ mảng mà lớn hơn cả số bên phải ngay lập tức và số bên trái ngay lập tức. Nếu tồn tại nhiều hơn một phần tử như vậy, hàm nên trả về bất kỳ cái nào.
Ví dụ:
Nếu mảng đầu vào là:
const arr = [3, 6, 7, 9, 8, 2, 5];
Thì đầu ra nên là:
const output = 9;
Vì câu hỏi yêu cầu tìm peak element, chúng ta có thể dùng phiên bản điều chỉnh của thuật toán tìm kiếm nhị phân.
Các bước sẽ là:
- Nhìn vào bất kỳ phần tử nào.
- Nếu phần tử tiếp theo và phần tử trước đó đều nhỏ hơn phần tử hiện tại, chúng ta tìm thấy giải pháp, trả về chỉ số hiện tại.
- Nếu phần tử tiếp theo lớn hơn phần tử hiện tại, chắc chắn có peak bên phải, nhìn đệ quy bên phải.
- Nếu phần tử trước đó lớn hơn phần tử hiện tại, chắc chắn có peak bên trái, nhìn đệ quy bên trái.
Ví dụ
Dưới đây là mã nguồn:
const arr = [3, 6, 7, 9, 8, 2, 5]; const greaterThanAdjacent = (arr = [], start = 0, end = arr.length) => { let mid = start + Math.floor((end - start) / 2); let curr = arr[mid]; let prev = mid-1 < 0 ? -Infinity : arr[mid-1]; let next = mid+1 > arr.length-1 ? -Infinity : arr[mid+1]; if (curr > prev && curr > next){ return arr[mid]; } if (curr < next){ return greaterThanAdjacent(arr, mid+1, end); } if (curr > next){ return greaterThanAdjacent(arr, start, mid-1); } return null; }; console.log(greaterThanAdjacent(arr));Kết quả
Đầu ra trên console:
9
Giải thích: Binary search tìm peak element (LeetCode 162). Điều kiện: arr[-1] = arr[n] = -∞. Nếu mid < mid+1 → peak ở bên phải. Else peak ở bên trái (kể cả mid). O(log n) time.