给定一个数组,找出每个元素的下一个较小元素

问题描述 投票:27回答:11

给定一个数组,为每个元素找到数组中的下一个较小元素,而不改变元素的原始顺序。

例如,假设给定的数组是4,2,1,5,3。

结果数组为2,1,-1,3,-1。

我在接受采访时被问到这个问题,但我想不出一个比普通的O(n ^ 2)解决方案更好的解决方案。我能想到的任何方法,即制作二元搜索树,或对数组进行排序,都会扭曲元素的原始顺序,从而导致错误的结果。

任何帮助将受到高度赞赏。

arrays algorithm
11个回答
40
投票

O(N)算法

  1. 将输出数组初始化为全-1。
  2. 创建我们在输入数组中访问过但尚未知道输出数组中的答案的空索引堆栈。
  3. 迭代输入数组中的每个元素: 它是否小于堆栈顶部索引的项目? 是。这是第一个这样的元素。填写输出数组中的相应元素,从堆栈中删除该项,然后再次尝试直到堆栈为空或答案为否。 不。继续3.2。 将此索引添加到堆栈。继续从3开始迭代。

Python实现

def find_next_smaller_elements(xs):
    ys=[-1 for x in xs]
    stack=[]
    for i,x in enumerate(xs):
        while len(stack)>0 and x<xs[stack[-1]]:
           ys[stack.pop()]=x
        stack.append(i)
    return ys

>>> find_next_smaller_elements([4,2,1,5,3])
[2, 1, -1, 3, -1]
>>> find_next_smaller_elements([1,2,3,4,5])
[-1, -1, -1, -1, -1]
>>> find_next_smaller_elements([5,4,3,2,1])
[4, 3, 2, 1, -1]
>>> find_next_smaller_elements([1,3,5,4,2])
[-1, 2, 4, 2, -1]
>>> find_next_smaller_elements([6,4,2])
[4, 2, -1]

说明

How it works

这是有效的,因为无论何时我们将一个项添加到堆栈,我们都知道它的值已经大于或等于堆栈中的每个元素。当我们访问数组中的元素时,我们知道如果它低于堆栈中的任何项目,它必须低于堆栈中的最后一项,因为最后一项必须是最大的。所以我们不需要在堆栈上进行任何类型的搜索,我们可以考虑最后一项。

注意:只要添加最后一步以清空堆栈并使用每个剩余索引将相应的输出数组元素设置为-1,就可以跳过初始化步骤。在创建它时,Python更容易将其初始化为-1s。

Time complexity

这是O(N)。主循环清楚地访问每个索引一次。每个索引只添加到堆栈一次,最多删除一次。

解决面试问题

这种问题在面试中可能会非常令人生畏,但我想指出(希望)面试官不会期望解决方案从你的脑海中完全形成。通过思考过程与他们交谈。我的事情是这样的:

  • 数字的位置与数组中下一个较小的数字之间是否存在某种关系?知道其中一些是否会限制其他人的可能性?
  • 如果我在白板前面,我可能会勾勒出示例数组并在元素之间绘制线条。我也可以将它们绘制为2D条形图 - 水平轴是输入数组中的位置,垂直轴是值。
  • 我有预感,这会显示一种模式,但没有纸张可以用。我认为图表会显而易见。仔细思考,我可以看到线条不会任意重叠,但只能嵌套。
  • 在这一点上,我突然意识到这与Python内部用于将缩进转换为INDENT和DEDENT虚拟标记的算法非常相似,我之前已经读过。请参阅“编译器如何解析缩进?”在这个页面上:http://www.secnetix.de/olli/Python/block_indentation.hawk然而,直到我实际制定了一个算法,我跟进了这个想法,并确定它实际上是相同的,所以我认为它没有太多帮助。尽管如此,如果你能看到与你知道的其他一些问题的相似之处,那么提一下这个问题可能是一个好主意,并说出它是如何相似的以及它是如何不同的。
  • 从这里开始,基于堆栈的算法的一般形状变得明显,但我仍然需要考虑更多,以确保它对那些没有后续较小元素的元素可以正常工作。

即使你没有提出一个有效的算法,试着让你的面试官看到你在想什么。通常,思维过程不仅仅是他们感兴趣的答案。对于一个棘手的问题,未能找到最佳解决方案但是能够洞察问题可能比知道一个罐头答案更好但却无法给予它更多分析。


0
投票

时间复杂性O(N),空间复杂性O(N)

java上的清洁解决方案保持数组的顺序:

public static int[] getNGE(int[] a) {
    var s = new Stack<Pair<Integer, Integer>>();
    int n = a.length;
    var result = new int[n];
    s.push(Pair.of(0, a[0]));

    for (int i = 1; i < n; i++) {
        while (!s.isEmpty() && s.peek().v2 > a[i]) {
            var top = s.pop();
            result[top.v1] = a[i];
        }
        s.push(Pair.of(i, a[i]));
    }

    while (!s.isEmpty()) {
        var top = s.pop();
        result[top.v1] = -1;
    }

    return result;
}

static class Pair<K, V> {
    K v1;
    V v2;

    public static  <K, V> Pair<K, V> of (K v1, V v2) {
        Pair p = new Pair();
        p.v1 = v1;
        p.v2 = v2;
        return p;
    }
}

-1
投票

具有O(1)空间复杂度和O(n)时间复杂度的解决方案。

void replace_next_smallest(int a[], int n)                                                          
    {                                                                                                   
        int ns = a[n - 1];                                                                              
        for (int i = n - 1; i >= 0; i--) {                                                              
            if (i == n - 1) {                                                                           
                a[i] = -1;                                                                              
            }                                                                                           
            else if (a[i] > ns) {                                                                       
                int t = ns;                                                                             
                ns = a[i];                                                                
                a[i] = t;                                                                               
            }                                                                                           
            else if (a[i] == ns) {                                                                      
                a[i] = a[i + 1];                                                                        
            }                                                                                           
            else {                                                                                      
                ns = a[i];                                                                              
                a[i] = -1;                                                                              
            }                                                                                           
        }                                                                                               
    }

3
投票

从阵列结束开始制作BST。对于每个值'v',答案将是您在插入'v'的过程中采用的最后一个节点“正确”,您可以轻松地以递归或迭代版本跟踪它。 更新:

根据您的要求,您可以以线性方式处理:

如果每个下一个元素都小于当前元素(例如6 5 4 3 2 1),则可以线性处理,而不需要任何额外的内存。当你开始得到混乱的元素时会出现有趣的情况(例如4 2 1 5 3),在这种情况下,只要你没有“得到'较小的对手',你就需要记住它们的顺序”。一个简单的基于堆栈的方法是这样的:

将第一个元素(a [0])推入堆栈。

对于每个下一个元素a [i],你可以看到堆栈,如果值(peek())大于a [i]中的值,你得到了该堆栈元素的下一个较小数字(peek()){并且只要peek()> a [i]}继续弹出元素。弹出它们并打印/存储相应的值。否则,只需将a [i]推回堆栈即可。

在最后,堆栈'll包含那些从未具有小于它们的值的元素(在它们的右边)。你可以在你的outpput中为他们填写-1。

例如A = [4,2,1,5,3];

stack: 4
a[i] = 2, Pop 4, Push 2 (you got result for 4)
stack: 2
a[i] = 1, Pop 2, Push 1 (you got result for 2)
stack: 1
a[i] = 5
stack: 1 5
a[i] = 3, Pop 5, Push 3 (you got result for 5)
stack: 1 3
1,3 don't have any counterparts for them. so store -1 for them.

2
投票

假设你的第一个下一个元素低于当前元素,这里有两个解决方案 -

  1. 使用sqrt(N)细分。将数组划分为sqrt(N)段,每段的长度为sqrt(N)。对于每个段,使用循环计算其最小元素。通过这种方式,您已预先计算了O(N)中每个段的最小元素。现在,对于每个元素,下一个下部元素可以与该一个元素在同一个片段中或在任何后续片段中。因此,首先检查当前段中的所有下一个元素。如果所有都更大,则循环遍历所有后续段以找出哪个元素具有低于当前元素的元素。如果你找不到,结果将是-1。否则,检查该段的每个元素以找出低于当前元素的第一个元素。总的来说,算法的复杂性是O(N*sqrt(N))O(N^1.5)

您可以使用具有类似方法的分段树来实现O(NlgN)

  1. 首先对数组进行排序(将元素的原始位置保持为卫星数据)。现在,假设数组的每个元素都是不同的,对于每个元素,我们需要找到该元素左侧的最低原始位置。这是一个经典的RMQ(Range Min Query)问题,可以通过多种方式解决,包括O(N)问题。由于我们需要先排序,整体复杂性是O(NlogN)。您可以了解更多有关RMQ in a TopCoder tutorial的信息。

1
投票

由于某些原因,我发现更容易推理“以前的小元素”,又名"all nearest smaller elements"。因此向后应用给出“下一个更小”。

为了记录,在O(n)时间,O(1)空间(即没有堆栈)的Python实现,支持数组中的负值:

def next_smaller(l):
    """ Return positions of next smaller items """
    res = [None] * len(l)
    for i in range(len(l)-2,-1,-1):
        j=i+1
        while j is not None and (l[j] > l[i]):
            j = res[j]
        res[i] = j
    return res

def next_smaller_elements(l):
    """ Return next smaller items themselves """
    res = next_smaller(l)
    return [l[i] if i is not None else None for i in res]

1
投票

这是javascript代码。这个video更好地解释了Algo

function findNextSmallerElem(source){
    let length = source.length;
    let outPut = [...Array(length)].map(() => -1);
    let stack = [];
    for(let i = 0 ; i < length ; i++){
        let stackTopVal = stack[ stack.length - 1] && stack[ stack.length - 1].val;
        // If stack is empty or current elem is greater than stack top
        if(!stack.length || source[i] > stackTopVal ){
            stack.push({ val: source[i], ind: i} );
        } else {
            // While stacktop is greater than current elem , keep popping
            while( source[i] < (stack[ stack.length - 1] && stack[ stack.length - 1].val) ){
                outPut[stack.pop().ind] = source[i];
            }
            stack.push({ val: source[i], ind: i} );
        }
    }
    return outPut;
}

输出 -

findNextSmallerElem([98,23,54,12,20,7,27])

[23, 12, 12, 7, 7, -1, -1]

0
投票

以下是我认为可以将其作为O(n log n)解决方案的观察结果。假设你有数组最后k个元素的答案。为了在此之前找出元素的值,您需要什么?您可以将最后的k个元素视为分成一系列范围,每个范围从某个元素开始并继续向前,直到它到达较小的元素。这些范围必须按降序排列,因此您可以考虑对它们进行二进制搜索,以找到小于该元素的第一个区间。然后,您可以更新范围以考虑此新元素。

现在,如何最好地代表这个?我想到的最好的方法是使用一个splay树,其键是定义这些范围的元素,其值是它们开始的索引。然后,您可以及时分摊O(log n)执行前任搜索以查找当前元素的前任。这会发现最早的值小于当前值。然后,在摊销的O(log n)时间内,将当前元素插入树中。这表示从该元素向前定义新范围。为了丢弃这个取代的所有范围,然后剪切新节点的右子节点,因为这是一个展开树位于树的根节点。

总的来说,这对总O(n lg n)的O(log n)过程进行O(n)次迭代。


0
投票

这是使用DP的O(n)算法(实际上是O(2n)):

int n = array.length();

数组min []记录从索引i到数组末尾的最小数量。

int[] min = new int[n];
min[n-1] = array[n-1];
for(int i=n-2; i>=0; i--)
   min[i] = Math.min(min[i+1],array[i]);

通过原始数组和min []进行搜索和比较。

int[] result = new int[n];
result[n-1] = -1;
for(int i=0; i<n-1; i++)
   result[i] = min[i+1]<array[i]?min[i+1]:-1;

这是找到“下一个更小的元素”的新解决方案:

int n = array.length();
int[] answer = new int[n];
answer[n-1] = -1;
for(int i=0; i<n-1; i++)
   answer[i] = array[i+1]<array[i]?array[i+1]:-1;

0
投票
        All that is actually not required i think

    case 1: a,b
    answer : -a+b

    case 2: a,b,c
    answer : a-2b+c

    case 3: a,b,c,d
    answer : -a+3b-3c+d

    case 4 :a,b,c,d,e
    answer : a-4b+6c-4d+e

    .
    .
    .
    recognize the pattern in it?
    it is the pascal's triangle!
                                   1
                                1     1
                              1    2     1
                           1    3     3     1
                        1    4     6     4     1
    so it can be calculated using Nth row of pascal's triangle!
    with alternate + ans - for odd even levels!
    it is O(1)

0
投票

您可以在O(n)运行时以O(n)空间复杂度解决此问题。从堆栈开始并继续推送元素,直到找到arr [i]使得arr [i] <stack.top元素。然后存储此索引。

代码片段:

vector<int> findNext(vector<int> values) {

    stack<int> st;
    vector<int> nextSmall(values.size(), -1);
    st.push(0);

    for (int i = 1; i < values.size(); i++) {
        while (!st.empty() && values[i] < values[st.top()]) {  
      // change values[i] < values[st.top()] to values[i] > values[st.top()] to find the next greater element.
            nextSmall[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }
     return nextSmall;
}
© www.soinside.com 2019 - 2024. All rights reserved.