← 전체 글로 돌아가기
competitive-programming2021년 12월 29일1분 분량

[LeetCode] 162. Find Peak Element 풀이

수정일: 2021년 12월 29일

Binary search
지원 언어:enko

#Problem

162. Find Peak Element

#Approach

이진탐색으로 nums[m]nums[m] 값과 양 옆의 값을 비교해준다.

  1. nums[m−1]>nums[m]nums[m-1] \gt nums[m] 이면:
    index mm 왼쪽에 peakpeak가 존재.
r <- m;
  1. nums[m]<nums[m+1]nums[m] \lt nums[m+1] 이면:
    index mm 오른쪽에 peakpeak가 존재.
l <- m+1;
  1. 둘다 아니면: index mm 자체가 peakpeak.
return m;

#Code

/**
 * written: 2021. 12. 29. Wed. 16:05:01 [UTC+9]
 * jooncco의 mac에서.
 **/

typedef vector<int> vi;

class Solution {
public:
    int findPeakElement(vi &nums) {
        int n= nums.size();
        // nums[-1]과 nums[n]이 -∞ 이므로 size가 1이면 자체가 peak
        if (n == 1) return 0;

        int l= 0, r= n-1;
        while (l < r) {
            int m= l+(r-l)/2;
            if (m > 0 && nums[m] < nums[m-1]) r= m;
            else if (m < n-1 && nums[m] < nums[m+1]) l= m+1;
            else return m;  // peak를 찾았으니 바로 return.
        }
        // l == peak index
        return l;
    }
};

#Complexity

  • Time: O(log⁡n)O(\log n)
  • Space: O(1)O(1)