c******n
发帖数: 4965 | 1 1. Given a array of integers , find 3 indexes i,j,k such that, i
] < a[j] < a[k]. Best possible is a O(n) algorithm.
这个就现在这样可以就设三个点，每个 新点来了对比这三个参照。就是写好些if else
但如果推广到 要求找K element 长的递增的subsequence， 怎么办？I guess u could
simply use "find the longest increasing subsequence", but if the actual LIS
is much longer than K, maybe simpler methods exist to simply find ONE
subsequence longer than K? | B******l
发帖数: 262 | 2 用一个stack，然后go through a，碰到a[i]把stack里大于等于a[i]的都pop出去，然
后push a[i]到stack，stack里的数是递增的，check stack size就行。复杂度O(n)。
[i
else
could
LIS
【在 c******n 的大作中提到】
: 1. Given a array of integers , find 3 indexes i,j,k such that, i: ] < a[j] < a[k]. Best possible is a O(n) algorithm.
: 这个就现在这样可以就设三个点，每个 新点来了对比这三个参照。就是写好些if else
: 但如果推广到 要求找K element 长的递增的subsequence， 怎么办？I guess u could
: simply use "find the longest increasing subsequence", but if the actual LIS
: is much longer than K, maybe simpler methods exist to simply find ONE
: subsequence longer than K?
| i******s
发帖数: 301 | 3 一个例子: [2, 3, 1, 4], 然后 k = 3
【在 B******l 的大作中提到】
: 用一个stack，然后go through a，碰到a[i]把stack里大于等于a[i]的都pop出去，然
: 后push a[i]到stack，stack里的数是递增的，check stack size就行。复杂度O(n)。
:
: [i
: else
: could
: LIS
| l******s
发帖数: 3045 | 4 stack size>1时不能pop
【在 B******l 的大作中提到】
: 用一个stack，然后go through a，碰到a[i]把stack里大于等于a[i]的都pop出去，然
: 后push a[i]到stack，stack里的数是递增的，check stack size就行。复杂度O(n)。
:
: [i
: else
: could
: LIS
| A******t
发帖数: 10 | 5 这样可以么 用两个数组 分别表示最大和最小的index 保持这两个数组是递减的
例如50， 60， 40， 30， 20， 35， 36；
min(的值) 50; 50; 50,40; 50,40,30; 50,40,30,20; 50,40,30,20
max(的值) ;60; 60; 60; 60; 60, , ,
35
int n = arr.length;
int[] min = new int[n];
int[] max = new int[n];
min[0] = 0;
int i = 0;
int j = -1;
for(int k=1; k
if(arr[k]
min[++i] = k;
}
else if(j>=0 && arr[min[i]]
arr[min[i]){ //介于二者中间
max[i] = arr[k];
j=i;
}
else if(j>=0 && arr[k]>arr[max[j]]){ //大于最大的 则找到
return i + "," + j + "," + k;
}
}
return "not found' | A*******e
发帖数: 2419 | 6 LIS，到k个就停止不行吗？
[i
else
could
LIS
【在 c******n 的大作中提到】
: 1. Given a array of integers , find 3 indexes i,j,k such that, i: ] < a[j] < a[k]. Best possible is a O(n) algorithm.
: 这个就现在这样可以就设三个点，每个 新点来了对比这三个参照。就是写好些if else
: 但如果推广到 要求找K element 长的递增的subsequence， 怎么办？I guess u could
: simply use "find the longest increasing subsequence", but if the actual LIS
: is much longer than K, maybe simpler methods exist to simply find ONE
: subsequence longer than K?
| c******n
发帖数: 4965 | 7 还没仔细看。 但k==2的时候， 你需要记录最低点（一个点）， k==3的时候，需要记
录前面两个点，如果又出现比前面阶梯的最低点还低的点， 还要记录新的最低点。
照这样照猫画虎， 那一般情况需要记录k-1个台阶，k-2个台阶，k-3个。。。。。1个
， 这k^个点把vertical space 分成k^2个区间都要比较
【在 A******t 的大作中提到】
: 这样可以么 用两个数组 分别表示最大和最小的index 保持这两个数组是递减的
: 例如50， 60， 40， 30， 20， 35， 36；
: min(的值) 50; 50; 50,40; 50,40,30; 50,40,30,20; 50,40,30,20
: max(的值) ;60; 60; 60; 60; 60, , ,
: 35
: int n = arr.length;
: int[] min = new int[n];
: int[] max = new int[n];
: min[0] = 0;
: int i = 0;
| S*****a
发帖数: 5 | 8 两个基本思路：
1、 先从简单入手， 找2个数而不是3个数， 看规律是啥。
2. 记得leetcode有道类似的题，是index进栈，而不是值进栈。
晚上再想想。
[i
else
could
LIS
【在 c******n 的大作中提到】
: 1. Given a array of integers , find 3 indexes i,j,k such that, i: ] < a[j] < a[k]. Best possible is a O(n) algorithm.
: 这个就现在这样可以就设三个点，每个 新点来了对比这三个参照。就是写好些if else
: 但如果推广到 要求找K element 长的递增的subsequence， 怎么办？I guess u could
: simply use "find the longest increasing subsequence", but if the actual LIS
: is much longer than K, maybe simpler methods exist to simply find ONE
: subsequence longer than K?
| h****3
发帖数: 89 | 9 貌似你这两个else if 永远也执行不了啊
【在 A******t 的大作中提到】
: 这样可以么 用两个数组 分别表示最大和最小的index 保持这两个数组是递减的
: 例如50， 60， 40， 30， 20， 35， 36；
: min(的值) 50; 50; 50,40; 50,40,30; 50,40,30,20; 50,40,30,20
: max(的值) ;60; 60; 60; 60; 60, , ,
: 35
: int n = arr.length;
: int[] min = new int[n];
: int[] max = new int[n];
: min[0] = 0;
: int i = 0;
| w***w
发帖数: 84 | 10 可以从左至右 scan 存当前见到的 “最小”递增序列 （对所有长从1到K）的值 这里
序列的大小是看最大的值 存在数组y里 然后每到一个新值 x 作 update 就是看如果x
介于y[k] 与y[k+1]之间 就设y[k+1]=x 因为y一定是单调减 可以做到 n log(K) 时间
K空间 | | | c******n
发帖数: 4965 | 11 见我上面帖子， 一个递增序列不够， 你怎么定义“最小”？序列第一个点最小？
how about
2 3 1 1.5 2
or
2 3. 1. 4
x
【在 w***w 的大作中提到】
: 可以从左至右 scan 存当前见到的 “最小”递增序列 （对所有长从1到K）的值 这里
: 序列的大小是看最大的值 存在数组y里 然后每到一个新值 x 作 update 就是看如果x
: 介于y[k] 与y[k+1]之间 就设y[k+1]=x 因为y一定是单调减 可以做到 n log(K) 时间
: K空间
| i***h
发帖数: 12655 | 12 如果有解，i，j，k
推论1。a[i] 是 ０－i里最小的， 否则可以被前面更小的数置换，同樣有解
推论2。a[k] 是 k－Ｎ里最大的， 否则可以被后面更大的数置换，同樣有解
算法：
同时从两头开始，前面存当前最小数a［i］，后面存当前最大数a［k］，如果a［i］>a
[k], 向中间移动
如果a［i］ | w***w
发帖数: 84 | 13 最大值 最后一个点
你的例子 y=（y[1],y[2],y[3]) 从左至右是 (2, null,null) (2,3,null) (1,3,null)
(1,1.5,null) (1,1.5,2) 所以存在递增3序列 | i***h
发帖数: 12655 | 14 最后那解法好象不行，修改一下
上面推论1和2继续成立
推论3，中间数a[j]同时不满足推论1和2
解法：
从头开始，标注所有当前最小数 － Ｎ
从尾巴倒退标注所有当前最大数 － Ｎ
再次遍历数组找到既沒有最小也沒有最大标记的数，如果找到，必然能以此为中间值找
到符合条件的i，j，k
否则无解
Ｏ（Ｎ）
>a
【在 i***h 的大作中提到】
: 如果有解，i，j，k
: 推论1。a[i] 是 ０－i里最小的， 否则可以被前面更小的数置换，同樣有解
: 推论2。a[k] 是 k－Ｎ里最大的， 否则可以被后面更大的数置换，同樣有解
: 算法：
: 同时从两头开始，前面存当前最小数a［i］，后面存当前最大数a［k］，如果a［i］>a
: [k], 向中间移动
: 如果a［i］
| c******n
发帖数: 4965 | 15 你这个例子里面有一步错了， 可以show 给你好像你对条件要求理解有误
2 3 1 1.5 2
2,null,null
2,3,null
1,3,null *********这一步有错，3 在 1前面， 不能算increasing sequence
null)
【在 w***w 的大作中提到】
: 最大值 最后一个点
: 你的例子 y=（y[1],y[2],y[3]) 从左至右是 (2, null,null) (2,3,null) (1,3,null)
: (1,1.5,null) (1,1.5,2) 所以存在递增3序列
| c******n
发帖数: 4965 | 16 如果你确实错了的话， point 就是现在检查到的 increasing sequence , 不仅要最低
（就像你说的以sequence top大小比较），另一个dimension 是已经积累的seqence 长
度，两个都要比较的话就成就了 LIS 的 n^2
【在 c******n 的大作中提到】
: 你这个例子里面有一步错了， 可以show 给你好像你对条件要求理解有误
: 2 3 1 1.5 2
: 2,null,null
: 2,3,null
: 1,3,null *********这一步有错，3 在 1前面， 不能算increasing sequence
:
: null)
| w***w
发帖数: 84 | 17 y[k]记的是到目前为至“最小”的长度为k的递增序列的最大值 所以 (1,3,null) 1 对
应长度为1的递增序列 （就是最小值）而3的对应序列是 2,3. | w***w
发帖数: 84 | 18 发个福利，上 code 吧 (这里k对应长为k+1的序列，POS_INFTY是上文中的null）这里
是从小到大比，是 O(nK) 时间。y 单调增，如果二分查找是 O(n log(K)).
bool has_K_increasing_sequence(vector X, int K) {
vector y(K, POS_INFTY);
for(double x: X) {
for(int k=0; k
if(x
}
}
return y[K-1] != POS_INFTY;
} | c******n
发帖数: 4965 | 19 很清晰，谢谢。
我开始总在想要记全部 k 个sequence , 那就有k^2 个区间要比较， 就想混了。 实际
只是max 管用。
【在 w***w 的大作中提到】
: 发个福利，上 code 吧 (这里k对应长为k+1的序列，POS_INFTY是上文中的null）这里
: 是从小到大比，是 O(nK) 时间。y 单调增，如果二分查找是 O(n log(K)).
: bool has_K_increasing_sequence(vector X, int K) {
: vector y(K, POS_INFTY);
: for(double x: X) {
: for(int k=0; k: if(x: }
: }
: return y[K-1] != POS_INFTY;
| c******n
发帖数: 4965 | 20 对比LIS 有一点有趣的相似： LIS 是在每一个前方的点都看partial increasing
sequence , 这里只管k 长的partial . LIS 还得记录partial 长度， 这里就直接
encode 到index 里面了
【在 c******n 的大作中提到】
: 很清晰，谢谢。
: 我开始总在想要记全部 k 个sequence , 那就有k^2 个区间要比较， 就想混了。 实际
: 只是max 管用。
| | | c******n
发帖数: 4965 | 21 用这个办法set K=N 就是这个 （最后一段）
http://www.algorithmist.com/index.php/Longest_Increasing_Subseq
【在 c******n 的大作中提到】
: 对比LIS 有一点有趣的相似： LIS 是在每一个前方的点都看partial increasing
: sequence , 这里只管k 长的partial . LIS 还得记录partial 长度， 这里就直接
: encode 到index 里面了
| l*****z
发帖数: 3022 | 22 一遍扫描的解法：
int[] check(int [] A){
int N = A.length;
if(N<3) return null;
int min = 0;
int[] ret = new int[3];
ret[0] = 0;
ret[1] = -1;
for(int i=1; i
if(ret[1] < 0){
if(A[i]
min = i;
ret[0] = i;
}else if(A[i]>A[min]){
ret[1] = i;
}
}
else{
//has i, j
if(A[i]>A[ret[1]]){
//found i , j, k
ret[2] = i;
return ret;
}else if(A[i]> A[ret[0]]){
ret[1] = i;
}else if(A[i] > A[min]){
ret[0] = min;
ret[1] = i;
}else if(A[i]
min = i;
}
}
}
return null;
} | i******s
发帖数: 301 | 23 赞思路。或者用O(n)空间，O(n)时间的，代码简单一点。LIS解法也行。这个需要分析
清楚为什么要保存min，赞
【在 l*****z 的大作中提到】
: 一遍扫描的解法：
: int[] check(int [] A){
: int N = A.length;
: if(N<3) return null;
: int min = 0;
: int[] ret = new int[3];
: ret[0] = 0;
: ret[1] = -1;
:
: for(int i=1; i
| s******x
发帖数: 417 | 24 赞一个！
【在 l*****z 的大作中提到】
: 一遍扫描的解法：
: int[] check(int [] A){
: int N = A.length;
: if(N<3) return null;
: int min = 0;
: int[] ret = new int[3];
: ret[0] = 0;
: ret[1] = -1;
:
: for(int i=1; i
|
|
