时间戳

首页 > 解决方案 > 查找数组中的下一个最小值？

arrays - 查找数组中的下一个最小值？

问题描述

这个问题一直困扰着我一段时间。基本上，如果您有一个输入数组 [4, 5, 2, 6, 7, 1]，则 4 和 5 的下一个最小数字是 2，而 6 和 7 的下一个最小数字是 1。我需要识别这些较小的数字。我有一个明显的 n^2 及时解决方案，但我觉得有一个 O(n) 及时解决方案。我需要对右边的下一个最小数字的存在采取行动，并在右边没有更小的数字的情况下采取行动。

我尝试过考虑动态编程解决方案和数据结构（特别是堆栈），但我似乎无法同时检查正确性和 O(n) 时间复杂度，其中一个似乎对我来说失败了。

有什么帮助吗？

标签： arrays

解决方案

您可以考虑为此使用堆栈数据结构。我已经用Java实现了它。这个想法是将索引推送到弹出，当堆栈中的顶部索引值大于数组的当前索引值时，弹出堆栈并将当前索引处的值分配给弹出的索引位置。

// Java Implementation of the idea
import java.util.Arrays;
import java.util.Stack;

public class NextSmallest{
    public static void main(String[] args) {
        int [] A = {4, 5, 2, 6, 7, 1};
        int [] ret = nextSmallest(A);
        System.out.println(Arrays.toString(ret)); // prints [2, 2, 1, 1, 1, 0]

    }

    static int [] nextSmallest(int [] A) {
        Stack<Integer> stack = new Stack<>();
        int n = A.length;
        int [] nextSmallestIndex = new int[n];
        for(int i = 0; i < n; i++) {
            while(!stack.isEmpty() && A[stack.peek()] > A[i]) {
                nextSmallestIndex[stack.pop()] = A[i];
            }
            stack.push(i);
        }
        return nextSmallestIndex;
    }
}

推荐阅读