很容易想出一个O(n)算法来解决这个非常著名的问题:
对于列表中的每个元素,找到比它大的第一个元素。这可以使用堆栈来完成。但是,如果我想找到大于 n*current 元素的第一个元素怎么办?
进一步来说:
给定一个数组 [2, 5, 4, 7, 3, 8, 9, 6] 并且 n = 2。
我想要 [5, -1, 9, -1, 8, -1, -1, -1] 对于 2, 5 是下一个大于 n * 2 的元素,对于 4, 9 是下一个大于 n * 的元素4. 对于 5,没有大于 n * 5 的元素,因此在该位置返回 -1。
我们能做得更好O(n^2)吗?