как найти ближайший меньший элемент в массиве?

Question

Я пытаюсь решить проблему ниже.

Given an array, find the nearest smaller element G[i] for every element A[i] in the array such that the element has an index smaller than i.

More formally,

    G[i] for an element A[i] = an element A[j] such that 
    j is maximum possible AND 
    j < i AND
    A[j] < A[i]
Elements for which no smaller element exist, consider next smaller element as -1.


Input Format

The only argument given is integer array A.
Output Format

Return the integar array G such that G[i] contains nearest smaller number than A[i].If no such element occurs G[i] should be -1.
For Example

Input 1:
    A = [4, 5, 2, 10, 8]
Output 1:
    G = [-1, 4, -1, 2, 2]
Explaination 1:
    index 1: No element less than 4 in left of 4, G[1] = -1
    index 2: A[1] is only element less than A[2], G[2] = A[1]
    index 3: No element less than 2 in left of 2, G[3] = -1
    index 4: A[3] is nearest element which is less than A[4], G[4] = A[3]
    index 4: A[3] is nearest element which is less than A[5], G[5] = A[3]

Input 2:
    A = [3, 2, 1]
Output 2:
    [-1, -1, -1]
Explaination 2:
    index 1: No element less than 3 in left of 3, G[1] = -1
    index 2: No element less than 2 in left of 2, G[2] = -1
    index 3: No element less than 1 in left of 1, G[3] = -1

Я пытался вот так

let prevSmaller = function(A){
    let min = A[0];
    for (let i = 0; i < A.length ; i++) {
        min = Math.min(min , A[i]);
        if(min == A[i]){
            A[i] = -1
        }else {
            A[i]= min
        }
    }
    return A
}

мой тест не пройден

вход: [34, 35, 27, 42, 5, 28, 39, 20, 28]

мой вывод:

[
  -1, 34, -1, 27, -1,
   5,  5,  5,  5
]

ожидаемый результат [-1, 34, -1, 27, -1, 5, 28, 5, 20]

Я думаю, что есть проблема в моем подходе. Можете ли вы сказать мне, пожалуйста другой подход, не могли бы вы сказать мне, где я делаю неправильно ..?

Answer 1

После долгой борьбы. Я смогу достичь этого используя stack

let prevSmaller = function(A){
    let stack = [],
        result = [];

    for (let i = 0; i < A.length ; i++) {
        while (stack.length !=0 && stack[stack.length -1] >= A[i]){
            stack.pop()
        }
        if(stack.length === 0) {
            result.push(-1)
        }else {
            result.push(stack[stack.length - 1 ])
        }
        stack.push(A[i])
    }
    return result
}