输出数组中每个元素右边最大的元素

Question

考虑Arr1 = [4, 6, 3, 9, 11, 5]

的输入

我想要一个以数组作为输入的函数。对于数组中的每个元素，它应该在其右侧输出第一个较大的值。

输出示例:4 - 6;6 - 9;3 - 9;9 - 1,11 - 1,5 - -1

需求:我想实现这个不使用嵌套的for循环。

---

for (i = 0,k = Arr1.length;i< k;i ++){
            var val = false;
            for(j=i+1;j<k;j++){
                while(Arr1[i] < Arr1[j] ){
                        console.log( Arr1[i] + " --" + Arr1[j]);
                        val = true;
                        break;
                }
                if(val){break;}
            }
            if( !val){
                console.log( Arr1[i] + " --" +" -1");
            }
        }

---

Answer 1

下面是一个示例。其思想是遍历数组，然后查看当前查找的元素之后的每个元素，直到找到一个更大的元素。较大的元素(默认为-1)被压入第二个数组中存储。

var Arr1 = [4, 6, 3, 9, 11, 5];
var Arr2 = [];
for (var i=0;i<Arr1.length;i++) {
    var biggerNumber = -1;
    for (var j=i+1;j<Arr1.length;j++) {
        if (Arr1[j]>Arr1[i]) {
            biggerNumber = Arr1[j];
            break;
        }
    }
    Arr2.push(biggerNumber);
}
//output: 
for(var i=0;i<Arr1.length;i++) {
    console.log(Arr1[i]+" -- "+Arr2[i]);
}

更新答案:

var Arr1 = [4, 6, 3, 9, 11, 5];
var stack=[];
Arr1.forEach(function(i){
    if (stack.length==0 || i<=stack[stack.length-1]) {
        stack.push(i);
    } else {
        while(stack.length>0 && i>stack[stack.length-1]) {
            console.log(i);
            stack.pop();
        }
        stack.push(i);
    }
});
stack.forEach(function(){console.log(-1);});

为什么它更好:内部循环总共执行Arr1.length次操作，所以它仍然在O(n)内运行。如何实现没有嵌套循环，我仍然不知道。