배열 왼쪽에 있는 가장 가까운 작은 요소

이 포스트에서 우리는 스택에 대한 매우 일반적인 질문을 탐구할 것입니다. 질문은 다음과 같습니다.

왼쪽의 가장 가까운 작은 요소

일부 요소가 포함된 배열/벡터/목록을 제공하고 배열의 왼쪽에서 가장 가까운 작은 요소를 찾는 것이 우리의 임무라고 가정해 보겠습니다.
예를 들어 :

let list = [ 4 , 10 , 5 , 8 , 20 , 15 , 3 , 12]
result = [-1 , 4 , 4 , 5 , 8 , 8 , -1 , 3] 

그리고 배열 오른쪽의 작은 요소

let list = [4 , 10 , 5 , 8 , 20 , 15 , 3 , 12]
result = [3 , 5 , 3 , 3 , 3 , 15 , 3 , 12 ]

문제를 해결하는 두 가지 방법이 있습니다.

무차별 대입 방식(중첩 루프 사용)

이 접근 방식에서는 두 개의 루프를 사용합니다. 외부 루프는 모든 배열 항목을 반복하고 내부 루프는 현재 외부 루프가 가리키는 모든 다음 요소를 반복합니다. 내부 루프가 검사하여 더 작은 요소가 발견되면 루프가 종료되고 더 작은 요소가 발견되지 않으면 결과로 -1이 추가됩니다.

function nearestSmallerToLeft(list) {
  let result = [];
  for (let indexOne = 0; indexOne < list.length; indexOne++) {
    let flag = false;
    for (let indexTwo = indexOne - 1; indexTwo > -1; indexTwo--) {
      if (arr[indexOne] > arr[indexTwo]) {
        result.push(arr[indexTwo]);
        flag = true;
        break;
      }
    }
    if (!flag) {
      result.push(-1);
    }
  }

  return result;
}

위 솔루션의 시간 복잡도는 O(n^2)
공간 복잡도는 추가 공간을 사용하지 않기 때문에 O(1)입니다.

스택 사용

이 접근 방식의 경우 스택을 사용합니다. 접근 방식은 주어진 배열의 요소를 처음부터 순회하는 것입니다. 즉, 맨 왼쪽 요소이며 스택에 가장 작은 요소를 넣고 다른 작은 요소를 얻을 때마다 스택을 팝하고 새 요소를 푸시합니다. 기본적으로 스택을 사용하여 왼쪽에서 더 작은 값을 사용할 수 있도록 합니다.

class Stack {
    constructor(){
        this.stack = [] ;
    }

    isEmpty() {
        return this.stack.length === 0;
    }
    push(element){
        this.stack.push(element);
    }
    pop(){
        if(this.isEmpty()){
            throw 'Stack UnderFlow';
        }
        return this.stack.pop();
    }

    top(){
        if(this.isEmpty())
        throw null ;
        return this.stack[this.stack.length-1];
    }
}


function nearestSmallerToLeft(list){
    const stack = new Stack();
    let result = [];

    for(let index = 0 ; index < list.length ; index++){

        if(stack.isEmpty()){
            result.push(-1);
            stack.push(list[index]);
        }
        else if(!stack.isEmpty()){
            while(!stack.isEmpty() && list[index]<stack.top()){
                stack.pop();
            }

            if(stack.isEmpty()){
                result.push(-1);
            }else{
                result.push(stack.top());
            }
            stack.push(arr[index]);
        }
    }

    return result ;
}

위 솔루션의 시간 복잡도는 스택에 추가 공간을 사용하므로 O(n) 및 공간 복잡도 O(n)입니다.