Find Peak Element

Question

  1. There is an integer array which has the following features:
  3.     * The numbers in adjacent positions are different.
  4.     * A[0] < A[1] && A[A.length - 2] > A[A.length - 1].
  6. We define a position P is a peek if A[P] > A[P-1] && A[P] > A[P+1].
  8. Find a peak element in this array. Return the index of the peak.
  10. Note
  11. The array may contains multiple peeks, find any of them.
  13. Example
  14. [1, 2, 1, 3, 4, 5, 7, 6]
  16. return index 1 (which is number 2)  or 6 (which is number 7)
  18. Challenge
  19. Time complexity O(logN)

題解1 - lintcode

由時間複雜度的暗示可知應使用二分搜索。首先分析若使用傳統的二分搜索，若A[mid] > A[mid - 1] && A[mid] < A[mid + 1]，則找到一個peak為A[mid]；若A[mid - 1] > A[mid]，則A[mid]左側必定存在一個peak，可用反證法證明：若左側不存在peak，則A[mid]左側元素必滿足A[0] > A[1] > ... > A[mid -1] > A[mid]，與已知A[0] < A[1]矛盾，證畢。同理可得若A[mid + 1] > A[mid]，則A[mid]右側必定存在一個peak。如此迭代即可得解。

備注：如果本題是找 first/last peak，就不能用二分法了。

Python

  1. class Solution:
  2.     #@param A: An integers list.
  3.     #@return: return any of peek positions.
  4.     def findPeak(self, A):
  5.         if not A:
  6.             return -1
  8.         l, r = 0, len(A) - 1
  9.         while l + 1 < r:
  10.             mid = l + (r - l) / 2
  11.             if A[mid] < A[mid - 1]:
  12.                 r = mid
  13.             elif A[mid] < A[mid + 1]:
  14.                 l = mid
  15.             else:
  16.                 return mid
  17.         mid = l if A[l] > A[r] else r
  18.         return mid

C++

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param A: An integers array.
  5.      * @return: return any of peek positions.
  6.      */
  7.     int findPeak(vector<int> A) {
  8.         if (A.size() == 0) return -1;
  10.         int l = 0, r = A.size() - 1;
  11.         while (l + 1 < r) {
  12.             int mid = l + (r - l) / 2;
  13.             if (A[mid] < A[mid - 1]) {
  14.                 r = mid;
  15.             } else if (A[mid] < A[mid + 1]) {
  16.                 l = mid;
  17.             } else {
  18.                 return mid;
  19.             }
  20.         }
  22.         int mid = A[l] > A[r] ? l : r;
  23.         return mid;
  24.     }
  25. };

Java

  1. class Solution {
  2.     /**
  3.      * @param A: An integers array.
  4.      * @return: return any of peek positions.
  5.      */
  6.     public int findPeak(int[] A) {
  7.         if (A == null || A.length == 0) return -1;
  9.         int l = 0, r = A.length - 1;
  10.         while (l + 1 < r) {
  11.             int mid = l + (r - l) / 2;
  12.             if (A[mid] < A[mid - 1]) {
  13.                 r = mid;
  14.             } else if (A[mid] < A[mid + 1]) {
  15.                 l = mid;
  16.             } else {
  17.                 return mid;
  18.             }
  19.         }
  21.         int mid = A[l] > A[r] ? l : r;
  22.         return mid;
  23.     }
  24. }

題解2 - leetcode

leetcode 上的題和 lintcode 上有細微的變化，題目如下：

  1. A peak element is an element that is greater than its neighbors.
  3. Given an input array where num[i] ≠ num[i+1],
  4. find a peak element and return its index.
  6. The array may contain multiple peaks,
  7. in that case return the index to any one of the peaks is fine.
  9. You may imagine that num[-1] = num[n] = -∞.
  11. For example, in array [1, 2, 3, 1], 3 is a peak element and
  12. your function should return the index number 2.
  14. click to show spoilers.
  16. Note:
  17. Your solution should be in logarithmic complexity.

如果一開始做的是 leetcode 上的版本而不是 lintcode 上的話，這道題難度要大一些。有了以上的分析基礎再來刷 leetcode 上的這道題就是小 case 了，注意題中的關鍵提示num[-1] = num[n] = -∞, 雖然不像 lintcode 上那麼直接，但是稍微變通下也能想到。即num[-1] < num[0] && num[n-1] > num[n], 那麼問題來了，這樣一來就不能確定峰值一定存在了，因為給定數組為單調序列的話就咩有峰值了，但是實際情況是——題中有負無窮的假設，也就是說在單調序列的情況下，峰值為數組首部或者尾部元素，誰大就是誰了。

C++

  1. class Solution {
  2. public:
  3.     int findPeakElement(vector<int>& arr) {
  4.         int N = arr.size();
  5.         int lo = 0, hi = N;
  6.         while(lo < hi) {
  7.             int mi = lo + (hi - lo)/2;
  8.             if( (mi == 0 || arr[mi-1] <= arr[mi] ) && (mi == N-1 || arr[mi] >= arr[mi+1]) ) 
  9.                 return mi;
  10.             else if((mi == 0 || arr[mi-1] <= arr[mi] ))
  11.                 lo = mi + 1;
  12.             else
  13.                 hi = mi;
  14.         }
  15.         return -1;
  16.     }
  17. };

Java

  1. public class Solution {
  2.     public int findPeakElement(int[] nums) {
  3.         if (nums == null || nums.length == 0) return -1;
  5.         int l = 0, r = nums.length - 1;
  6.         while (l + 1 < r) {
  7.             mid = l + (r - l) / 2;
  8.             if (nums[mid] < nums[mid - 1]) {
  9.                 // 1 peak at least in the left side
  10.                 r = mid;
  11.             } else if (nums[mid] < nums[mid + 1]) {
  12.                 // 1 peak at least in the right side
  13.                 l = mid;
  14.             } else {
  15.                 return mid;
  16.             }
  17.         }
  19.         mid = nums[l] > nums[r] ? l : r;
  20.         return mid;
  21.     }
  22. }

源碼分析

典型的二分法模板應用，需要注意的是需要考慮單調序列的特殊情況。當然也可使用緊湊一點的實現如改寫循環條件為l < r，這樣就不用考慮單調序列了，見實現2.

複雜度分析

二分法，時間複雜度 O(\log n).

Java - compact implementation[^leetcode_discussion]

  1. public class Solution {
  2.     public int findPeakElement(int[] nums) {
  3.         if (nums == null || nums.length == 0) {
  4.             return -1;
  5.         }
  7.         int start = 0, end = nums.length - 1, mid = end / 2;
  8.         while (start < end) {
  9.             if (nums[mid] < nums[mid + 1]) {
  10.                 // 1 peak at least in the right side
  11.                 start = mid + 1;
  12.             } else {
  13.                 // 1 peak at least in the left side
  14.                 end = mid;
  15.             }
  16.             mid = start + (end - start) / 2;
  17.         }
  19.         return start;
  20.     }
  21. }

C++ 的代碼可參考 Java 或者 @xuewei4d 的實現。

Warning leetcode 和 lintcode 上給的方法名不一樣，leetcode 上的為findPeakElement而 lintcode 上為findPeak，弄混的話會編譯錯誤。

Reference