[LeetCode] Arrays101 - Valid Mountain Array

Valid Mountain Array

Given an array of integers arr, return true if and only if it is a valid mountain array.

Recall that arr is a mountain array if and only if:

• 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]

Example 1:

Input: arr = [2,1]
Output: false

Example 2:

Input: arr = [3,5,5]
Output: false

Example 3:

Input: arr = [0,3,2,1]
Output: true

Constraints:

• 1 <= arr.length <= 104
• 0 <= arr[i] <= 104

 

---

 

이 번주에 푼 문제들 중에 제일 재밌었던 문제여서 가져와봤다.

 

배열의 숫자들이 마치 산(⛰)처럼 중간으로 갈 수록 크기가 커지고,

끝으로 갈 수록 다시 크기가 작아지는 형태인지 아닌지 판별하는 문제이다.

 

물론 중간에 크기가 같은 숫자가 있거나,

혹은 작아졌다 커졌다 여러 번 반복하면 탈락..!

 

이거는 문제가 그래도 비교적 쉬워서 금방 풀었는데,

다음과 같이 풀었다.

 

/**
 * @param {number[]} arr
 * @return {boolean}
 */
var validMountainArray = function(arr) {
  if (arr.length < 3) return false;

  let start = 0;
  let end = arr.length - 1;

  while (arr[start] < arr[start + 1]) {
    start++;
  }

  while (arr[end - 1] > arr[end]) {
    end--;
  }
  
  if (start === end) {
    if (start === 0) return false;
    if (start === arr.length - 1) return false;
    
    return true;
  }
  return false;
};

 

앞에서부터 배열의 다음 아이템이 현재의 아이템보다 크기가 작아지기 전까지 반복한다. 반복이 끝나면 해당 index를 기억해둔다.

그 다음, 뒤에서부터 이 전 아이템이 현재의 아이템보다 크기가 커지기 전까지 반복하고, 똑같이 반복이 끝나면 index를 기억한다.

 

두 index가 같으면서 0이나 배열의 마지막 index가 아니라면 true를, 나머지는 false를 리턴한다.

 

* 두 index가 모두 0이라면 해당 배열은 [5, 4, 3, 2, 1]과 같이 내림차순 배열이다.

* 두 index가 모두 배열의 마지막 index라면 해당 배열은 [1, 2, 3, 4, 5]와 같이 오름차순 배열이다.