紧急求助：可以拿单篇文章的引用于ＥＳＩ的top percentage 比吗？# Immigration - 落地生根
c*n
1 楼
http://www.lintcode.com/en/problem/max-tree/
needs O(N) time. naiive scanning the array for maximum value at each layer,
leads to NlogN time.
for example A[0] ... A[9]
I could do a maxPointToLeft[] array and maxPointToRight[] array, so given
maxPointToRight[0], I can find the max at level 0, say i=5
then at level 1, for the left sub arr, A[0 .. 4], I can find max by
maxPointToLeft[4], say i=2, but then at level 2, to find the max of A[3 ..
4], I have to scan entire range of 3 .. 4.
so I have to refill the maxPointToLeft[] again. luckily the time reduces by
1/2 at every level, so we manage to get to O(N) but this looks rather ugly.
any better ideas?
needs O(N) time. naiive scanning the array for maximum value at each layer,
leads to NlogN time.
for example A[0] ... A[9]
I could do a maxPointToLeft[] array and maxPointToRight[] array, so given
maxPointToRight[0], I can find the max at level 0, say i=5
then at level 1, for the left sub arr, A[0 .. 4], I can find max by
maxPointToLeft[4], say i=2, but then at level 2, to find the max of A[3 ..
4], I have to scan entire range of 3 .. 4.
so I have to refill the maxPointToLeft[] again. luckily the time reduces by
1/2 at every level, so we manage to get to O(N) but this looks rather ugly.
any better ideas?
