假设我有一个这样的阵列查找下一次出现的每个元素在阵列:[ 1, 2, 3, 4, 5, 6, 1]
在O(N)
我想获得像1 ==输出> 6(对于元件1(0 第索引匹配在索引6)
这意味着0 第元件下一个匹配是在第六指数发现找到。
如果输入是[4,6,4,6]
输出是4 ==> 2和6 = => 3
由于用于4第一匹配索引2(其为四)和第一发现匹配六(2 第二元件)在3 RD索引
发现如果时间复杂度是O(n )解决方案非常简单。我试图用O(n)中的代码在栈中找到下一个最好的元素。但我无法找到一种方法来为下一个相同的元素做同样的事情。
import java.util.Scanner;
import java.util.Stack;
public class NextGreatestElement {
public static void main(String[] args) {
int[] inp = {1,4,6,2,39};
Stack<Integer> stack = new Stack<>();
stack.push(inp[0]);
for (int i = 1; i < inp.length; i++) {
int element = inp[i];
if (element > stack.peek()) {
System.out.println(stack.peek() + " ==> " + element);
stack.pop();
while (!stack.isEmpty()) {
System.out.println(stack.pop() + " ==> " + element);
}
stack.push(element);
} else if (element < stack.peek()) {
stack.push(element);
}
}
while (!stack.isEmpty()) System.out.println(stack.pop() + " ==> " + (-1));
}
}
即使算法就足够了。我不需要代码。
是什么'未来最大element'是什么意思? – Eran
对于这个输入[1,2,3,4,5,6,1],下一个最大的元素是1,它是2和2,它是3,依此类推,六中没有什么是 – bharath
您可以实现的最佳复杂度是O(nlogn),使用快速排序对数组进行排序,然后遍历它以找到数组中没有更大后继的元素。 –