JavaScript의 원형 배열에서 다음으로 큰 요소

원형 배열

마지막 요소의 다음 요소가 배열의 첫 번째 요소인 배열을 종종 원형이라고 합니다.

분명히, 이와 같은 데이터를 저장하는 메커니즘은 없으며 데이터는 여전히 연속 메모리 블록에 저장되며 원형 배열은 현실보다 아이디어에 가깝습니다.

문제

첫 번째이자 유일한 인수로 정수의 순환 배열인 arr을 취하는 JavaScript 함수를 작성해야 합니다.

그런 다음 함수는 원래 배열의 각 해당 요소에 대해 다음으로 큰 요소를 포함하는 배열을 생성하고 반환해야 합니다. 숫자의 다음 큰 수, 예를 들어 num은 배열에서 순회 순서(우리의 경우 오른쪽)에 대한 첫 번째 큰 숫자입니다. 즉, 순환적으로 검색하여 다음 큰 숫자를 찾을 수 있습니다. 존재하지 않는 경우 이 숫자에 대해 -1을 고려해야 합니다.

예를 들어, 함수에 대한 입력이 -

const arr = [7, 8, 7];

그러면 출력은 다음과 같아야 합니다. -

const output = [8, -1, 8];

출력 설명

배열에서 7보다 다음으로 큰 것은 8이고 배열이 원형이기 때문에 8의 경우 더 큰 요소가 없으므로 -1을 넣습니다.

예시

이에 대한 코드는 -

const arr = [7, 8, 7];
const nextGreaterElement = (arr = []) => {
   const res = [];
   const stack = [];
   if (!arr || arr.length < 1){
      return res;
   };
   for (let i = 0; i < arr.length; i++) {
      while (stack.length > 0 && arr[stack[stack.length - 1]] < arr[i]) {
         const small = stack.pop();
         res[small] = arr[i];
      };
      stack.push(i);
   }
   for (let i = 0; i < arr.length; i++) {
      while (stack.length > 0 && arr[stack[stack.length - 1]] < arr[i]) {
         const small = stack.pop();
         res[small] = arr[i];
      };
   }
   const rem = stack.length;
   for (let i = 0; i < rem; i++) {
      res[stack.pop()] = -1;
      }
      return res;
   };
console.log(nextGreaterElement(arr));

코드 설명:

배열을 반복하는 동안 스택에서 하나보다 큰 요소를 찾으면 res[small]을 현재 발견된 더 큰 요소로 설정합니다.

이제 우리는 다시 arr의 시작 부분에서 시작하여 이전 for 루프에서 다음으로 더 큰 요소를 찾을 수 없었던 요소를 처리합니다. 마지막으로, 여전히 다음으로 큰 요소가 없는 일부 요소가 있을 것입니다.

출력

콘솔의 출력은 -

[8, -1, 8]