找找看这里面谁是老江湖# Joke - 肚皮舞运动M*a2013-08-30 07:081 楼给定一个数组,未必sorted的,找最长subarray使得这个subarray average小于一个值k怎么做没有O(N^2)好的不用说了哦
f*42013-08-30 07:083 楼考虑前缀和的数组s[0..n]的下标a=s[b],那么如果s[b..c]满足均值么s[a...c]也一定满足,所以这里是单调的.于是可以从左到右建严格递增的下标序列(用stack即可), answer的开始值肯定在这些之中.结束位置也类似,但只需维护一个最小且最右的下标即可.这样就是O(N)【在 M*******a 的大作中提到】: 给定一个数组,未必sorted的,找最长subarray使得这个subarray average小于一个值: k: 怎么做: 没有O(N^2)好的不用说了哦
M*a2013-08-30 07:085 楼兄台水平不错么【在 f*******4 的大作中提到】: 考虑前缀和的数组s[0..n]的下标a=s[b],那么如果s[b..c]满足均值: 么s[a...c]也一定满足,所以这里是单调的.: 于是可以从左到右建严格递增的下标序列(用stack即可), answer的开始值肯定在这些: 之中.: 结束位置也类似,但只需维护一个最小且最右的下标即可.这样就是O(N)
x*i2013-08-30 07:087 楼这个前缀和的数组是怎么定义的?可以给个具体例子解释下吗?谢谢!【在 f*******4 的大作中提到】: 考虑前缀和的数组s[0..n]的下标a=s[b],那么如果s[b..c]满足均值: 么s[a...c]也一定满足,所以这里是单调的.: 于是可以从左到右建严格递增的下标序列(用stack即可), answer的开始值肯定在这些: 之中.: 结束位置也类似,但只需维护一个最小且最右的下标即可.这样就是O(N)
m*42013-08-30 07:089 楼不好意思没有看懂这个解法。大牛能否多展开说说?【在 f*******4 的大作中提到】: 考虑前缀和的数组s[0..n]的下标a=s[b],那么如果s[b..c]满足均值: 么s[a...c]也一定满足,所以这里是单调的.: 于是可以从左到右建严格递增的下标序列(用stack即可), answer的开始值肯定在这些: 之中.: 结束位置也类似,但只需维护一个最小且最右的下标即可.这样就是O(N)
J*32013-08-30 07:0811 楼前缀数组:preSum[i] = A[i] + A[i-1] +...A[0]O(n), 从后向前扫一遍确定单调递增的数组同样O(n)【在 x*******i 的大作中提到】: 这个前缀和的数组是怎么定义的?: 可以给个具体例子解释下吗?谢谢!
w*s2013-08-30 07:0812 楼s[a]>=s[b] 应该是 s[a] <= s[b] ?“考虑前缀和的数组s[0..n]的下标a=s[b],那么如果s[b..c]满足均值么s[a...c]也一定满足,所以这里是单调的.于是可以从左到右建严格递增的下标序列(用stack即可), answer的开始值肯定在这些之中.结束位置也类似,但只需维护一个最小且最右的下标即可.这样就是O(N)”
y*32013-08-30 07:0813 楼这个没看懂。。跪求哪位好心的前辈给解释一下,帮帮菜鸟。谢谢!【在 f*******4 的大作中提到】: 考虑前缀和的数组s[0..n]的下标a=s[b],那么如果s[b..c]满足均值: 么s[a...c]也一定满足,所以这里是单调的.: 于是可以从左到右建严格递增的下标序列(用stack即可), answer的开始值肯定在这些: 之中.: 结束位置也类似,但只需维护一个最小且最右的下标即可.这样就是O(N)
f*e2013-08-30 07:0814 楼sounds interesting!【在 f*******4 的大作中提到】: 考虑前缀和的数组s[0..n]的下标a=s[b],那么如果s[b..c]满足均值: 么s[a...c]也一定满足,所以这里是单调的.: 于是可以从左到右建严格递增的下标序列(用stack即可), answer的开始值肯定在这些: 之中.: 结束位置也类似,但只需维护一个最小且最右的下标即可.这样就是O(N)
w*s2013-08-30 07:0815 楼这个解法应该是错的。我这里提供一个O(n)的方法,看看还有没有改进空间。假设原题的数组是a,长度是n,我们先计算出一个辅助数组b,长度是n,b[i] = a[i]- k, 对0 <= i < n那么原题就转化为在b中求一个最长的连续子序列,和小于0在此基础上,计算s[i] = b[0] + b[1] + ... + b[i - 1] 对于 0 <= i <= n连续子序列b[i] + b[i + 1] + ... + b[j] = s[j + 1] - s[i] 对于 0 <= i,j < n对于题目所求,我们希望s[i]越大越好,s[j + 1]越小越好,这样他们的差才会小对于s数组,长度为n+1,从右到左扫描一遍,记录严格递减的元素,添加记录到一个数组(stack)c,然后从左到右再扫描一遍,记录扫描过的最大值,与c最后一个元素比较,看其差是否满足题目要求,若是则记录最优解,当扫描过c的最后一个元素时,则将c的最后一个元素移出。这样需要扫描两边,空间复杂度是O(n),因为需要额外的数组s和c。【在 f*******4 的大作中提到】: 考虑前缀和的数组s[0..n]的下标a=s[b],那么如果s[b..c]满足均值: 么s[a...c]也一定满足,所以这里是单调的.: 于是可以从左到右建严格递增的下标序列(用stack即可), answer的开始值肯定在这些: 之中.: 结束位置也类似,但只需维护一个最小且最右的下标即可.这样就是O(N)
b*e2013-08-30 07:0816 楼你这个和fabregas4的解法是一模一样的。你说的更清晰一些罢了。]较,【在 w*******s 的大作中提到】: 这个解法应该是错的。: 我这里提供一个O(n)的方法,看看还有没有改进空间。: 假设原题的数组是a,长度是n,我们先计算出一个辅助数组b,长度是n,b[i] = a[i]: - k, 对0 <= i < n: 那么原题就转化为在b中求一个最长的连续子序列,和小于0: 在此基础上,计算s[i] = b[0] + b[1] + ... + b[i - 1] 对于 0 <= i <= n: 连续子序列b[i] + b[i + 1] + ... + b[j] = s[j + 1] - s[i] 对于 0 <= i,j < n: 对于题目所求,我们希望s[i]越大越好,s[j + 1]越小越好,这样他们的差才会小: 对于s数组,长度为n+1,从右到左扫描一遍,记录严格递减的元素,添加记录到一个数: 组(stack)c,然后从左到右再扫描一遍,记录扫描过的最大值,与c最后一个元素比较,
b*e2013-08-30 07:0817 楼牛逼。不得不出来顶一下。这个不容易想到。面试的时候谁能做出来这个那绝对是天人合一。【在 f*******4 的大作中提到】: 考虑前缀和的数组s[0..n]的下标a=s[b],那么如果s[b..c]满足均值: 么s[a...c]也一定满足,所以这里是单调的.: 于是可以从左到右建严格递增的下标序列(用stack即可), answer的开始值肯定在这些: 之中.: 结束位置也类似,但只需维护一个最小且最右的下标即可.这样就是O(N)
w*s2013-08-30 07:0818 楼后半部分是一样的,前面的部分他没有转换,所以有点问题。【在 b***e 的大作中提到】: 你这个和fabregas4的解法是一模一样的。你说的更清晰一些罢了。: : ]: 较,
m*i2013-08-30 07:0820 楼fabregas4的明显有问题。度没有用到小于k这个条件【在 z******6 的大作中提到】: 这两个解法本质上是一样的,fabregas4还比westmites少个辅助数组b。
m*i2013-08-30 07:0821 楼]较,只和c最后一个元素比较O(N)找出来的不是最长的。最长的估计要 O(NlgN)【在 w*******s 的大作中提到】: 这个解法应该是错的。: 我这里提供一个O(n)的方法,看看还有没有改进空间。: 假设原题的数组是a,长度是n,我们先计算出一个辅助数组b,长度是n,b[i] = a[i]: - k, 对0 <= i < n: 那么原题就转化为在b中求一个最长的连续子序列,和小于0: 在此基础上,计算s[i] = b[0] + b[1] + ... + b[i - 1] 对于 0 <= i <= n: 连续子序列b[i] + b[i + 1] + ... + b[j] = s[j + 1] - s[i] 对于 0 <= i,j < n: 对于题目所求,我们希望s[i]越大越好,s[j + 1]越小越好,这样他们的差才会小: 对于s数组,长度为n+1,从右到左扫描一遍,记录严格递减的元素,添加记录到一个数: 组(stack)c,然后从左到右再扫描一遍,记录扫描过的最大值,与c最后一个元素比较,
w*s2013-08-30 07:0822 楼确实是O(n),但是我之前没有想清楚最后扫描的时候修改c的方法,现在已经在原帖上修正了。【在 m******i 的大作中提到】: : ]: 较,: 只和c最后一个元素比较O(N)找出来的不是最长的。最长的估计要 O(NlgN)
x*a2013-08-30 07:0823 楼这个O(n) 是建立在数组全部都是正数的情况下, 如果有正有负, 这个跟严格递增没有关系, egsum[i] = {-100, 1, -100, 2, -100, 3, -100, 4, 1, -1}最长sub array就是用[0...n-1]还是我理解有错?]较,【在 w*******s 的大作中提到】: 这个解法应该是错的。: 我这里提供一个O(n)的方法,看看还有没有改进空间。: 假设原题的数组是a,长度是n,我们先计算出一个辅助数组b,长度是n,b[i] = a[i]: - k, 对0 <= i < n: 那么原题就转化为在b中求一个最长的连续子序列,和小于0: 在此基础上,计算s[i] = b[0] + b[1] + ... + b[i - 1] 对于 0 <= i <= n: 连续子序列b[i] + b[i + 1] + ... + b[j] = s[j + 1] - s[i] 对于 0 <= i,j < n: 对于题目所求,我们希望s[i]越大越好,s[j + 1]越小越好,这样他们的差才会小: 对于s数组,长度为n+1,从右到左扫描一遍,记录严格递减的元素,添加记录到一个数: 组(stack)c,然后从左到右再扫描一遍,记录扫描过的最大值,与c最后一个元素比较,
w*s2013-08-30 07:0824 楼没看懂你啥意思,不过O(n)是对于数组有正有负都一样的。【在 x*****a 的大作中提到】: 这个O(n) 是建立在数组全部都是正数的情况下, 如果有正有负, 这个跟严格递增没有: 关系, eg: sum[i] = {-100, 1, -100, 2, -100, 3, -100, 4, 1, -1}: 最长sub array就是用[0...n-1]: 还是我理解有错?: : ]: 较,
x*y2013-08-30 07:0825 楼His approach is right, except he needs to substract k from each elementfirst; otherwise, his statement "s[0..n]的下标a=s[b],那么如果s[b..c]满足均值【在 m******i 的大作中提到】: fabregas4的明显有问题。度没有用到小于k这个条件
m*i2013-08-30 07:0826 楼妙!大牛指教了!上修【在 w*******s 的大作中提到】: 确实是O(n),但是我之前没有想清楚最后扫描的时候修改c的方法,现在已经在原帖上修: 正了。
f*42013-08-30 07:0827 楼stack和最后元素x维护的都是下标. 所以判断时检查 (s[x]-s[stack.top()])/(x-stack.top())和k的大小关系【在 w*******s 的大作中提到】: 后半部分是一样的,前面的部分他没有转换,所以有点问题。
w*s2013-08-30 07:0828 楼我觉得是错的【在 f*******4 的大作中提到】: stack和最后元素x维护的都是下标. 所以判断时检查 (s[x]-s[stack.top()])/(x-: stack.top())和k的大小关系
b*e2013-08-30 07:0829 楼不必纠缠于细节。他的意思就是说求的是各点到y = kx的距离,而不是到y = 0的距离。那个大方向上的思路是对的。【在 w*******s 的大作中提到】: 我觉得是错的
n*f2013-08-30 07:0831 楼我觉得你的算法实际上是贪心法。递减点(右-左)减去最大点(左到右),不一定得到最优解。]较,【在 w*******s 的大作中提到】: 这个解法应该是错的。: 我这里提供一个O(n)的方法,看看还有没有改进空间。: 假设原题的数组是a,长度是n,我们先计算出一个辅助数组b,长度是n,b[i] = a[i]: - k, 对0 <= i < n: 那么原题就转化为在b中求一个最长的连续子序列,和小于0: 在此基础上,计算s[i] = b[0] + b[1] + ... + b[i - 1] 对于 0 <= i <= n: 连续子序列b[i] + b[i + 1] + ... + b[j] = s[j + 1] - s[i] 对于 0 <= i,j < n: 对于题目所求,我们希望s[i]越大越好,s[j + 1]越小越好,这样他们的差才会小: 对于s数组,长度为n+1,从右到左扫描一遍,记录严格递减的元素,添加记录到一个数: 组(stack)c,然后从左到右再扫描一遍,记录扫描过的最大值,与c最后一个元素比较,
n*f2013-08-30 07:0832 楼“对于题目所求,我们希望s[i]越大越好,s[j + 1]越小越好,这样他们的差才会小”我觉得这个不对。这样求出来的是平均值较小的,而不是满足条件的最长的subarray。有时候,s[j+1+1]对应的数a[j+1](不是递减点),由于a[j+1]较小,但是跟前面的suarray平均下,依旧满足条件。愚见而已,还请大神们指点。
w*s2013-08-30 07:0833 楼早知道leetcode上有,就不用费时间写了老大半天了。【在 c********e 的大作中提到】: http://leetcode.com/2011/05/a-distance-maximizing-problem.html
w*s2013-08-30 07:0834 楼你没看懂,前面有人贴了leetcode的题解,你可以参考一下。【在 n******f 的大作中提到】: “对于题目所求,我们希望s[i]越大越好,s[j + 1]越小越好,这样他们的差才会小”: 我觉得这个不对。这样求出来的是平均值较小的,而不是满足条件的最长的subarray。: 有时候,s[j+1+1]对应的数a[j+1](不是递减点),由于a[j+1]较小,但是跟前面的: suarray平均下,依旧满足条件。: 愚见而已,还请大神们指点。