j*****y
发帖数: 1071 | 1 能做到 O(n) time 和 O(1) space 吗？
只想到 O(n) time 和 O(n) space. |
s****0
发帖数: 117 | 2 longest increasing subsequence
http://en.wikipedia.org/wiki/Longest_increasing_subsequence
limit the size of the stack to 3. |
j*****y
发帖数: 1071 | 3 时间能有 O(n) 吗？
【在 s****0 的大作中提到】
: longest increasing subsequence
: http://en.wikipedia.org/wiki/Longest_increasing_subsequence
: limit the size of the stack to 3.
|
s****0
发帖数: 117 | 4 Did you read the algorithm yet?
the time complexity of the original version is O(n*lgn). The log n comes
from the binary search of the stack. In this case, it is const time. |
j*****y
发帖数: 1071 | 5 多谢 :)
【在 s****0 的大作中提到】
: Did you read the algorithm yet?
: the time complexity of the original version is O(n*lgn). The log n comes
: from the binary search of the stack. In this case, it is const time.
|
P***t
发帖数: 1006 | 6 3个指针就行。
先update x, y 指向第一个顺排的pair.
另外一指针z 用来指向x y之后一个比 x 更小的数。
z = -1
for (i = y + 1; y < len; y++)
if A[i] > A[y]
we are done! return A[x], A[y], A[i].
else if A[i] > A[x] && A[i] < A[y]
y = i
else if A[i] < A[x]
{
if z >= 0 && A[i] > A[z]
x = z
y = i
z = -1
else
z = i
} |
b***e
发帖数: 1419 | 7 我顶一下这个。这个不错。
【在 P***t 的大作中提到】
: 3个指针就行。
: 先update x, y 指向第一个顺排的pair.
: 另外一指针z 用来指向x y之后一个比 x 更小的数。
: z = -1
: for (i = y + 1; y < len; y++)
: if A[i] > A[y]
: we are done! return A[x], A[y], A[i].
: else if A[i] > A[x] && A[i] < A[y]
: y = i
: else if A[i] < A[x]
|
s****9
发帖数: 43 | 8
【在 b***e 的大作中提到】
: 我顶一下这个。这个不错。
|
s****9
发帖数: 43 | 9
谁能详细说说怎么 做呀
【在 s****9 的大作中提到】
|
z******t
发帖数: 59 | 10 有O(n) time 和O(1) space 的解法。
写了篇博客讨论这个问题：
http://codercareer.blogspot.com/2013/02/no-42-three-increasing-
【在 j*****y 的大作中提到】
: 能做到 O(n) time 和 O(1) space 吗？
: 只想到 O(n) time 和 O(n) space.
|
