162. Find Peak Element

• github: https://github.com/choijiwoong/LeetCode/blob/main/LeetCode75/162.%20Find%20Peak%20Element.java

---

(24.12.13)

• 문제 이해: 이웃보다 큰 원소의 인덱스를 반환하라. 이 때 시간복잡도는 O(logn)이어야 한다.

• 문제 접근 1: O(logn)이면 일반적인 순회가 아닌 이진탐색을 사용하라는 문제로 보인다. 이진 탐색을 하려면 우선 정렬상태여야한다. 가장 먼저 생각나는 방법은 원소와 인덱스를 묶어 정렬시킨 수, 큰 수에서부터 내려가며 이웃한 수보다 큰 경우를 찾는 것이다. 하지만 이 경우 최악의 경우 O(n)이 된다.

• 문제 접근 2: 만약 Tree에 i-1, i, i+1 노드 단위로 넣는다면..?

• 문제 접근 3: 문득 문제 접근 2를 수행하기 전에 문제 구조 상 무조건 최댓값이 이웃의 최댓값이 될 것 같아서 그 인덱스를 구하는 코드를 테스트 해보았는데 패스되어 제출해보았더니 통과되었다.

class Solution{
	public int findPeakElement(int[] nums){
    	return IntStream.range(0, nums.length) // 인덱스 배열을 만들고
        	.reduce((a,b)->nums[a]>nums[b]?a:b) // 원소값을 비교하며 1개 값만 남김
            .orElse(-1);//예외처리
    }
}

• 공부 1: 다른 사람들이 제출한 코드를 살펴보자. 왜 이진탐색을 한걸까? 정렬도 안되어 있는 값인데..? GPT에게 물어보니 피크(극댓값)은 무조건 올라가는 경사에서 내려가는 경사로 바뀌는 경우에 발생한다. 고로 mid값을 기준으로 mid+1과 비교했을 때 mid가 더 크다면 내려가는 경사, mid가 더 작다면 올라가는 경사임을 알 수 있다. 그런데 여기서 또다른 의문이 생기는데, 저 코드에서 지역 극댓값과 전체 극댓값을 어떻게 구분할 수 있는 걸까? GPT에게 물어보니 저 코드로 전체 극댓값을 계산할 수 없다고 한다. 문제를 다시 확인해보니 "any of the peaks"의 인덱스를 리턴하라고 한다.

class Solution {
    public int findPeakElement(int[] nums) {
        int n = nums.length - 1;
        int low = 0; 
        int high = n;
        while(low < high) {
            int mid = low + (high - low)/2;
            if (nums[mid] > nums[mid+1]) {//ascending slope
              high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
}

새로이 이해한 내용을 바탕으로 코드를 구현해봤는데, 쉽지 않았다.

class Solution {
    public int findPeakElement(int[] nums) {
        int start=0, end=nums.length-1, mid=0;//1,2,1
        while(start<end){
            mid=(start+end)/2;
            if(nums[mid+1]>mid){
                start=mid+1;
            } else{
                end=mid-1;
            }
        }
        return mid;
    }
}