[LeetCode] 852. Peak Index in a Mountain Array

https://leetcode.com/problems/peak-index-in-a-mountain-array/description/

Peak Index in a Mountain Array - LeetCode

문제 유형 : 배열

문제 난이도 : Medium

 

문제

An array arr a mountain if the following properties hold:

• arr.length >= 3
• There exists some i with 0 < i < arr.length - 1 such that:
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given a mountain array arr, return the index i such that arr[0] < arr[1] < ... < arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1].

You must solve it in O(log(arr.length)) time complexity.

 

원소의 값이 산의 형태를 가진 배열이 주어집니다. 이 배열의 산봉우리 인덱스를 구하시오.

시간복잡도O(N)이내로 문제를 해결하시오.

풀이

배열을 순회하면서 가장 높은 값을 가진 값과 인덱스를 갱신하면서 순회한다.

한 번이라도 다음 값이 낮아지면(내리막을 감지하면), 순회를 멈춘다

 

코드(C++)

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);

        const int n = arr.size();
        int peakIndex = -1;
        int peakHeight = -1;

        for(int i = 0; i < n; i++){
            if(arr[i] > peakHeight){
                peakHeight = arr[i];
                peakIndex = i;
            }
            else{
                break;
            }
        }
        return peakIndex;
    }
};