M*******a 发帖数: 1633 | 1 给定一个数组,未必sorted的,找最长subarray使得这个subarray average小于一个值
k
怎么做
没有O(N^2)好的不用说了哦 |
f*******4 发帖数: 64 | 2 考虑前缀和的数组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*******a 发帖数: 1633 | 3 兄台水平不错么
【在 f*******4 的大作中提到】 : 考虑前缀和的数组s[0..n]的下标a=s[b],那么如果s[b..c]满足均值: 么s[a...c]也一定满足,所以这里是单调的. : 于是可以从左到右建严格递增的下标序列(用stack即可), answer的开始值肯定在这些 : 之中. : 结束位置也类似,但只需维护一个最小且最右的下标即可.这样就是O(N)
|
x*******i 发帖数: 26 | 4 这个前缀和的数组是怎么定义的?
可以给个具体例子解释下吗?谢谢!
【在 f*******4 的大作中提到】 : 考虑前缀和的数组s[0..n]的下标a=s[b],那么如果s[b..c]满足均值: 么s[a...c]也一定满足,所以这里是单调的. : 于是可以从左到右建严格递增的下标序列(用stack即可), answer的开始值肯定在这些 : 之中. : 结束位置也类似,但只需维护一个最小且最右的下标即可.这样就是O(N)
|
m**********4 发帖数: 774 | 5 不好意思没有看懂这个解法。大牛能否多展开说说?
【在 f*******4 的大作中提到】 : 考虑前缀和的数组s[0..n]的下标a=s[b],那么如果s[b..c]满足均值: 么s[a...c]也一定满足,所以这里是单调的. : 于是可以从左到右建严格递增的下标序列(用stack即可), answer的开始值肯定在这些 : 之中. : 结束位置也类似,但只需维护一个最小且最右的下标即可.这样就是O(N)
|
J****3 发帖数: 427 | 6 前缀数组:
preSum[i] = A[i] + A[i-1] +...A[0]
O(n), 从后向前扫一遍确定单调递增的数组同样O(n)
【在 x*******i 的大作中提到】 : 这个前缀和的数组是怎么定义的? : 可以给个具体例子解释下吗?谢谢!
|
w*******s 发帖数: 96 | 7 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*****3 发帖数: 451 | 8 这个没看懂。。
跪求哪位好心的前辈给解释一下,帮帮菜鸟。谢谢!
【在 f*******4 的大作中提到】 : 考虑前缀和的数组s[0..n]的下标a=s[b],那么如果s[b..c]满足均值: 么s[a...c]也一定满足,所以这里是单调的. : 于是可以从左到右建严格递增的下标序列(用stack即可), answer的开始值肯定在这些 : 之中. : 结束位置也类似,但只需维护一个最小且最右的下标即可.这样就是O(N)
|
f********e 发帖数: 91 | 9 sounds interesting!
【在 f*******4 的大作中提到】 : 考虑前缀和的数组s[0..n]的下标a=s[b],那么如果s[b..c]满足均值: 么s[a...c]也一定满足,所以这里是单调的. : 于是可以从左到右建严格递增的下标序列(用stack即可), answer的开始值肯定在这些 : 之中. : 结束位置也类似,但只需维护一个最小且最右的下标即可.这样就是O(N)
|
w*******s 发帖数: 138 | 10 这个解法应该是错的。
我这里提供一个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***e 发帖数: 1419 | 11 你这个和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***e 发帖数: 1419 | 12 牛逼。不得不出来顶一下。这个不容易想到。面试的时候谁能做出来这个那绝对是天人
合一。
【在 f*******4 的大作中提到】 : 考虑前缀和的数组s[0..n]的下标a=s[b],那么如果s[b..c]满足均值: 么s[a...c]也一定满足,所以这里是单调的. : 于是可以从左到右建严格递增的下标序列(用stack即可), answer的开始值肯定在这些 : 之中. : 结束位置也类似,但只需维护一个最小且最右的下标即可.这样就是O(N)
|
w*******s 发帖数: 138 | 13 后半部分是一样的,前面的部分他没有转换,所以有点问题。
【在 b***e 的大作中提到】 : 你这个和fabregas4的解法是一模一样的。你说的更清晰一些罢了。 : : ] : 较,
|
z******6 发帖数: 37 | 14 这两个解法本质上是一样的,fabregas4还比westmites少个辅助数组b。 |
m******i 发帖数: 6 | 15 fabregas4的明显有问题。度没有用到小于k这个条件
【在 z******6 的大作中提到】 : 这两个解法本质上是一样的,fabregas4还比westmites少个辅助数组b。
|
m******i 发帖数: 6 | 16
]
较,
只和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*******s 发帖数: 138 | 17 确实是O(n),但是我之前没有想清楚最后扫描的时候修改c的方法,现在已经在原帖上修
正了。
【在 m******i 的大作中提到】 : : ] : 较, : 只和c最后一个元素比较O(N)找出来的不是最长的。最长的估计要 O(NlgN)
|
x*****a 发帖数: 9 | 18 这个O(n) 是建立在数组全部都是正数的情况下, 如果有正有负, 这个跟严格递增没有
关系, eg
sum[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*******s 发帖数: 138 | 19 没看懂你啥意思,不过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***y 发帖数: 633 | 20 His approach is right, except he needs to substract k from each element
first; otherwise, his statement "s[0..n]的下标a=s[b],那么如果s[b
..c]满足均值
【在 m******i 的大作中提到】 : fabregas4的明显有问题。度没有用到小于k这个条件
|
|
|
m******i 发帖数: 6 | 21 妙!大牛指教了!
上修
【在 w*******s 的大作中提到】 : 确实是O(n),但是我之前没有想清楚最后扫描的时候修改c的方法,现在已经在原帖上修 : 正了。
|
f*******4 发帖数: 64 | 22 stack和最后元素x维护的都是下标. 所以判断时检查 (s[x]-s[stack.top()])/(x-
stack.top())和k的大小关系
【在 w*******s 的大作中提到】 : 后半部分是一样的,前面的部分他没有转换,所以有点问题。
|
w*******s 发帖数: 138 | 23 我觉得是错的
【在 f*******4 的大作中提到】 : stack和最后元素x维护的都是下标. 所以判断时检查 (s[x]-s[stack.top()])/(x- : stack.top())和k的大小关系
|
b***e 发帖数: 1419 | 24 不必纠缠于细节。他的意思就是说求的是各点到y = kx的距离,而不是到y = 0的距离
。那个大方向上的思路是对的。
【在 w*******s 的大作中提到】 : 我觉得是错的
|
c********e 发帖数: 186 | |
n******f 发帖数: 318 | 26 我觉得你的算法实际上是贪心法。递减点(右-左)减去最大点(左到右),不一定得
到最优解。
]
较,
【在 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******f 发帖数: 318 | 27 “对于题目所求,我们希望s[i]越大越好,s[j + 1]越小越好,这样他们的差才会小”
我觉得这个不对。这样求出来的是平均值较小的,而不是满足条件的最长的subarray。
有时候,s[j+1+1]对应的数a[j+1](不是递减点),由于a[j+1]较小,但是跟前面的
suarray平均下,依旧满足条件。
愚见而已,还请大神们指点。 |
w*******s 发帖数: 138 | |
w*******s 发帖数: 138 | 29 你没看懂,前面有人贴了leetcode的题解,你可以参考一下。
【在 n******f 的大作中提到】 : “对于题目所求,我们希望s[i]越大越好,s[j + 1]越小越好,这样他们的差才会小” : 我觉得这个不对。这样求出来的是平均值较小的,而不是满足条件的最长的subarray。 : 有时候,s[j+1+1]对应的数a[j+1](不是递减点),由于a[j+1]较小,但是跟前面的 : suarray平均下,依旧满足条件。 : 愚见而已,还请大神们指点。
|