如何找到数组中给定索引的前一个最小元素？

Question

例如，我有一个

input array 
[1,3,5,6,4,8,4,3,2,1]

output should be [-1 , 1, 3, 5, 3 , 6, 3, 1, 1, -1]

解释： 让我们将第一个元素保留为 -1，因为之前没有更小的元素。

In index '1' the previous smaller element to 3 needs to be stored. i.e 1.

In index '2' the previous smaller element to 5 needs to be stored. i.e 3. & so on...

我知道我可以在 O(n2) 复杂度内解决这个问题。但我想以 O(n) 复杂度解决这个问题。我试过了，还是不行。

请帮我解决这个问题。提前致谢。

Answer 1

我想你想在 O(n) 时间内解决它。您可以在这里找到答案：https://www.geeksforgeeks.org/find-the-nearest-smaller-numbers-on-left-side-in-an-array/

Answer 2

O(n) 可能是不可能的，但我可以给你 O(n log n) 的方法。创建平衡的 BST（大多数编程语言中的 set/dictionary 结构）。您现在可以通过遍历树轻松找到小于 x 的最大数字。

Set/dictionary 结构通常有一个称为上限的内置函数，它会找到大于 x 的最小元素（如果你决定更改排序顺序，则找到最大的元素）。你也可以用那个。

您只需：

对于数组中的每个值 v：

求BST中小于v的最大数,
将 v 插入 BST

Answer 3

 //NEAREST SMALLEST TO LEFT'S INDEX
    //CREATE A NEW STACK
    Stack<Integer> stack = new Stack<>();
    //ARRAY TO STORE OUTPUT VALUES
    int[] ans = new int[n];
    //TRAVERSE FROM LEFT TO RIGHT OF INPUT ARRAY
    for(int i=0; i<n; i++){
        //HERE WE PERFORM 3 OPERATIONS
        /* 1ST) WHILE STACK IS NOT EMPTY
        IF YOU FIND ANYTHING >= TO ARR[I] POP*/
        while(!stack.empty() && arr[stack.peek()] >= arr[i]){
            stack.pop();
        }
        /* 2ND) IF STACK IS EMPTY RETURN -1 
          (WHATEVER AS PER YOUR NEED) */
        if(stack.empty()){
            ans[i] = -1;
        }
        /* 3RD) WE FOUND NEAREST SMALLEST TO LEFT */
        else{
            ans[i] = stack.peek();
        }
        //PUSH INDEX TO STACK
        stack.push(i);
       
    }

如何找到数组中给定索引的前一个最小元素？

How to find previous smallest element of a given index in the array?

algorithm

dynamic-programming

recursive-datastructures

data-structures