Java 单调对 - Codility
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/23113268/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Monotonic Pair - Codility
提问by Whizzil
I was just at Codility, and ran into a task for which I can't find a solution in targeted O(n) efficiency; my solution runs for O(n2). I would be very pleased if someone could just give me a hint on how to get it run faster. Here is the task.
我刚在 Codility 工作，遇到了一项任务，我无法找到具有目标 O(n) 效率的解决方案；我的解决方案运行时间为 O(n2)。如果有人能给我一个如何让它运行得更快的提示，我会非常高兴。这是任务。
A non-empty zero-indexed array A consisting of N integers is given.
给出了一个由 N 个整数组成的非空零索引数组 A。
A monotonic_pair is a pair of integers (P, Q), such that 0 ≤ P ≤ Q < N and A[P] ≤ A[Q].
monotonic_pair 是一对整数 (P, Q)，使得 0 ≤ P ≤ Q < N 且 A[P] ≤ A[Q]。
The goal is to find the monotonic_pair whose indices are the furthest apart. More precisely, we should maximize the value Q ? P. It is sufficient to find only the distance.
目标是找到索引相距最远的 monotonic_pair。更准确地说，我们应该最大化 Q 值？P. 只找到距离就足够了。
For example, consider array A such that:
例如，考虑数组 A 使得：
A[0] = 5
A[1] = 3
A[2] = 6
A[3] = 3
A[4] = 4
A[5] = 2
There are eleven monotonic_pairs: (0,0), (0, 2), (1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (3, 3), (3, 4), (4, 4), (5, 5). The biggest distance is 3, in the pair (1, 4).
有十一个 monotonic_pairs: (0,0), (0, 2), (1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (3, 3), (3, 4), (4, 4), (5, 5)。最大的距离是 3，在对 (1, 4) 中。
Write a function:
写一个函数：
class Solution { public int solution(int[] A); }
类解决方案{ public int 解决方案(int[] A); }
that, given a non-empty zero-indexed array A of N integers, returns the biggest distance within any of the monotonic_pairs.
给定一个由 N 个整数组成的非空零索引数组 A，返回任何 monotonic_pairs 内的最大距离。
For example, given:
例如，给定：
A[0] = 5
A[1] = 3
A[2] = 6
A[3] = 3
A[4] = 4
A[5] = 2
the function should return 3, as explained above.
如上所述，该函数应返回 3。
Assume that:
假使，假设：
N is an integer within the range [1..300,000]; each element of array A is an integer within the range [?1,000,000,000..1,000,000,000]. Complexity:
N 是 [1..300,000] 范围内的整数；数组 A 的每个元素都是 [?1,000,000,000..1,000,000,000] 范围内的整数。复杂：
expected worst-case time complexity is O(N); expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments). Elements of input arrays can be modified.
预期的最坏情况时间复杂度为 O(N)；预期的最坏情况空间复杂度为 O(N)，超出输入存储（不包括输入参数所需的存储）。可以修改输入数组的元素。
And my 1st idea solution (runs in O(n2)):
我的第一个想法解决方案（在 O(n2) 中运行）：
public static int solution(int[] A) {
int max = 0;
for(int i=0; i<A.length-1; i++) {
for(int j=i+1; j<A.length; j++) {
if(A[j] >= A[i] &&
(j - i) >= max) {
max = j - i;
}
}
}
return max;
}
采纳答案by MarcinLe
Create a temporary array containing maximum values in descending order:
按降序创建一个包含最大值的临时数组：
int[] top = new int[A.length];
int max = -Integer.MAX_VALUE;
for (int i=A.length-1; i>=0; i--) {
if (A[i] > max) max = A[i];
top[i] = max;
}
so you can quickly find them with binary search:
所以你可以通过二分搜索快速找到它们：
int find(int[] t, int min) {
int s = 0;
int e = t.length-1;
if (t[e] >= min) return e;
while (true) {
int x = (s+e) / 2;
if (x == t.length-1) return t.length-1;
if (t[x] >= min && t[x+1] < min) return x;
if (t[x] < min) e = x;
else s = x;
}
}
And you got a solution:
你有一个解决方案：
int best = 0;
for (int i=0; i<A.length; i++) {
int c = find(top, A[i]) - i;
if (c > best) best = c;
if (best >= A.length-i) return best;
}
return best;
回答by pliashkou
There is also another algorithm, based on finding maximum distance between pairs (sorry, PHP), it also has O(n2) complexity:
还有另一种算法，基于寻找对之间的最大距离（对不起，PHP），它也有 O(n2) 复杂度：
function solution($a) {
$length = count($a);
for($max = $length-1; $max > 0; $max-- ) {
for($i = 0; $i < $length - $max ; $i++) {
if ($a[$i] <= $a[$i+$max]) {
return $max;
}
}
}
return 0;
}
回答by Bruno Gallien
I think you have to think in terms of distance. It is like the breadth first search. Look for all the couple that have the max distance ( being the size of the array ) then the ones with distance - 1 and so on. I am working on it and will try to come with a c++ solution.
我认为你必须考虑距离。这就像广度优先搜索。查找所有具有最大距离（即数组的大小）的对，然后是距离为 1 的对，依此类推。我正在研究它，并将尝试提供 C++ 解决方案。
回答by Phil Anderson
MarcinLe's is better than n^2, but still runs in nlogn. You can optimize by not doing your logn lookup every time. Instead, iterate forward over your max array and your input A[] array at the same time to guarantee linear time.
MarcinLe 比 n^2 好，但仍然在 nlogn 中运行。您可以通过不每次都执行 logn 查找来优化。相反，同时向前迭代最大数组和输入 A[] 数组以保证线性时间。
int[] top = new int[A.length];
int max = -Integer.MAX_VALUE;
for (int i=A.length-1; i>=0; i--) {
if (A[i] > max) max = A[i];
top[i] = max;
}
int best = 0;
int curMaxIndex = 0;
for (int i=0; i<A.length; i++) {
while(curMaxIndex < top.length && top[curMaxIndex] >= A[i])
curMaxIndex++;
if((curMaxIndex - 1 - i) > best)
best = curMaxIndex - 1 - i
}
return best;
回答by Chris
I came across the similar test and chose to resolve it in C. I believe my solution runs as O(nlog(n)) worst case and O(1) best case. Now I use O(1) loosely, but it's very possible.
我遇到了类似的测试并选择在 C 中解决它。我相信我的解决方案运行为 O(nlog(n)) 最坏情况和 O(1) 最佳情况。现在我松散地使用 O(1)，但这很有可能。
Basically I worked with 2 pointers. One moving slowly from tail of the array, and one scanning against each found from the head. I immediately break from the loop on the pairs whose indices are the furthest apart which happen to be the ones calculated first using this method.
基本上我使用了 2 个指针。一个从阵列的尾部缓慢移动，一个从头部扫描发现。我立即从索引相距最远的对上的循环中断，这些对恰好是首先使用此方法计算的那些。
O(1) becomes possible because if the first monotonic pair you calculate happens to be at the end and head of the list, then that is your answer. There is no possible value larger then this to return.
O(1) 成为可能，因为如果您计算的第一个单调对恰好位于列表的末尾和开头，那么这就是您的答案。没有可能的值大于 this 返回。
int solution(int A[], int N) {
// write your code in C90
int p,q;
// forward and backwards iterators
int fi,bi=N-1;
// track largest difference
int diff=0;
// interate through entire loop
for(; bi >= 0; --bi){
// Initialization
p=q=bi;
fi=0;
// looking from the front
for(fi=0; fi<bi; fi++){
if(A[fi] <= A[p] && A[q] >= A[fi] && fi<bi){
p=fi;
break;
}
}
if(diff < (q-p)){
diff = (q-p);
}
if(diff >= bi){
break;
}
}
return diff;
}
回答by Durgaprasad Budhwani
My Solution But got 66%. Its O(n**2) time complexity. Code is in JavaScript.
我的解决方案但得到了 66%。它的 O(n**2) 时间复杂度。代码在 JavaScript 中。
function solution(A) {
var N = A.length;
var distance = 0;
for(var i = 0; i < N-1; i++) {
for(var j = i; j < N; j++){
if(A[i] <= A[j] && (j - i) > distance)
distance = j - i;
}
}
return distance;
}
