为数组中的每个元素查找下一个大于或等于该元素两倍的元素

Question

算法描述：

对于输入数组的每个元素，找到下一个大于或等于该元素两倍的元素。

换句话说，对于 i, j，其中 j>i

输出[i]=输入[j]，当且仅当，输入[j]>=2*输入[i]

示例：

idx:     0   1   2   3   4   5   6
Input:  23, 35, 12, 47, 33, 68, 34
Output: 47, -1, 47, -1, 68, -1, -1

说明：

对于 idx=3，没有元素大于或等于 47 的两倍，即 >=94

对于 idx=4，68(idx=5) 大于 47

有人可以建议我一个比 O(n^2) 具有更好时间复杂度的算法吗？

Answer 1

您可以反向迭代，同时保持单调堆栈。要获得每个输出，请在堆栈的元素中进行二分搜索，以查找至少是当前元素两倍的最接近元素。这导致总时间复杂度为

O(n log n)

。

Java 实现示例：

public static int[] solve(int[] input) {
    int[] output = new int[input.length], stk = new int[input.length];
    int top = -1;
    for (int i = input.length - 1; i >= 0; i--) {
        int low = 0, high = top;
        while (low <= high) {
            int mid = low + high >>> 1;
            if (stk[mid] < 2 * input[i]) high = mid - 1;
            else low = mid + 1;
        }
        output[i] = high < 0 ? -1 : stk[high];
        while (top >= 0 && input[i] >= stk[top]) --top;
        stk[++top] = input[i];
    }
    return output;
}