162. Find Peak Element
Tags:
Medium
Skills:
Binary Search
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu tìm một peak element trong mảng số nguyên, tức là một phần tử lớn hơn cả hai phần tử lân cận (nếu có)
Nếu có nhiều đỉnh, return về chỉ số bất kỳ của một đỉnh. Đề bài đảm bảo luôn tồn tại ít nhất một đỉnh và các phần tử kề nhau khác nhau
Approach - Binary search
mid với phần tử bên phải mid + 1 nums[mid] > nums[mid + 1] , đỉnh nằm ở bên trái (bao gồm cả mid), vì có thể mid chính là đỉnh hoặc đỉnh nằm bên tráinums[mid] < nums[mid + 1], đỉnh nằm ở bên phải (không bao gồm mid), vì bên phải có phần tử lớn hơnTại sao lại chắc chắn có đỉnh ở đoạn còn lại?
Infinity, nên luôn tồn tại ít nhất một đỉnh.Solution
1function findPeakElement(nums: number[]): number {
2 let left = 0, right = nums.length - 1
3 while (left < right) {
4 const mid = left + Math.floor((right - left) / 2);
5 if (nums[mid] > nums[mid + 1]) right = mid;
6 else left = mid + 1;
7 }
8 return left;
9};