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平均下，依旧满足条件。
: 愚见而已，还请大神们指点。
|
