설명

오름차순으로 정렬되고 일부 피벗점에서 회전되는 고유 정수 목록nums이 제공됩니다. 회전된 목록에서 최대 개수를 찾습니다.

O(log*n*)로 해결할 수 있나요?

제약 조건:

n ≤ 100,000 여기서 n는 nums의 길이입니다.

예 1

입력

arr = [6, 7, 8, 1, 4]

산출

arr = [6, 7, 8, 1, 4]

설명

The original sorted array of [1, 4, 6, 7, 8] was rotated at index 2 and results in the input array [6, 7, 8, 1, 4,]. And the largest number is 8.

예 2

입력

arr = [1, 2, 3]

산출

3

예 3

입력

arr = [1]

산출

1

예시 4

입력

arr = [10, 1, 2, 3, 4, 7]

산출

10

직관

이진 검색

if (arr[mid+1] < arr[mid]) , mid 는 가장 큰 값 인덱스

구현

import java.util.*;

class Solution {
    // Time=O(logn), space=O(1)
    public int solve(int[] arr) {
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 0....mid, mid+1....right
            if (mid + 1 < arr.length && arr[mid + 1] < arr[mid]) {
                return arr[mid];
            }
            if (arr[left] <= arr[mid]) {
                // left side sorted
                // 8,9,10,4,5,6
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return arr[left];
    }
}

시간 복잡도

시간: O(logn)

스페이스: O(1)