Redian新闻
>
找找看这里面谁是老江湖
avatar
找找看这里面谁是老江湖# Joke - 肚皮舞运动
M*a
1
给定一个数组,未必sorted的,找最长subarray使得这个subarray average小于一个值
k
怎么做
没有O(N^2)好的不用说了哦
avatar
k*r
2
avatar
f*4
3
考虑前缀和的数组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)好的不用说了哦

avatar
l*t
4
2黑1灰
avatar
M*a
5
兄台水平不错么

【在 f*******4 的大作中提到】
: 考虑前缀和的数组s[0..n]的下标a=s[b],那么如果s[b..c]满足均值: 么s[a...c]也一定满足,所以这里是单调的.
: 于是可以从左到右建严格递增的下标序列(用stack即可), answer的开始值肯定在这些
: 之中.
: 结束位置也类似,但只需维护一个最小且最右的下标即可.这样就是O(N)

avatar
M*9
6
同意

【在 l****t 的大作中提到】
: 2黑1灰
avatar
x*i
7
这个前缀和的数组是怎么定义的?
可以给个具体例子解释下吗?谢谢!

【在 f*******4 的大作中提到】
: 考虑前缀和的数组s[0..n]的下标a=s[b],那么如果s[b..c]满足均值: 么s[a...c]也一定满足,所以这里是单调的.
: 于是可以从左到右建严格递增的下标序列(用stack即可), answer的开始值肯定在这些
: 之中.
: 结束位置也类似,但只需维护一个最小且最右的下标即可.这样就是O(N)

avatar
c*n
8
太有喜感了
avatar
m*4
9
不好意思没有看懂这个解法。大牛能否多展开说说?

【在 f*******4 的大作中提到】
: 考虑前缀和的数组s[0..n]的下标a=s[b],那么如果s[b..c]满足均值: 么s[a...c]也一定满足,所以这里是单调的.
: 于是可以从左到右建严格递增的下标序列(用stack即可), answer的开始值肯定在这些
: 之中.
: 结束位置也类似,但只需维护一个最小且最右的下标即可.这样就是O(N)

avatar
d*l
10
这仨反射弧太长,过了10秒才反应过来,就被你们认为是老江湖了?

【在 l****t 的大作中提到】
: 2黑1灰
avatar
J*3
11
前缀数组:
preSum[i] = A[i] + A[i-1] +...A[0]
O(n), 从后向前扫一遍确定单调递增的数组同样O(n)

【在 x*******i 的大作中提到】
: 这个前缀和的数组是怎么定义的?
: 可以给个具体例子解释下吗?谢谢!

avatar
w*s
12
s[a]>=s[b] 应该是 s[a] <= s[b] ?

考虑前缀和的数组s[0..n]的下标a=s[b],那么如果s[b..c]满足均值么s[a...c]也一定满足,所以这里是单调的.
于是可以从左到右建严格递增的下标序列(用stack即可), answer的开始值肯定在这些
之中.
结束位置也类似,但只需维护一个最小且最右的下标即可.这样就是O(N)”
avatar
y*3
13
这个没看懂。。
跪求哪位好心的前辈给解释一下,帮帮菜鸟。谢谢!

【在 f*******4 的大作中提到】
: 考虑前缀和的数组s[0..n]的下标a=s[b],那么如果s[b..c]满足均值: 么s[a...c]也一定满足,所以这里是单调的.
: 于是可以从左到右建严格递增的下标序列(用stack即可), answer的开始值肯定在这些
: 之中.
: 结束位置也类似,但只需维护一个最小且最右的下标即可.这样就是O(N)

avatar
f*e
14
sounds interesting!

【在 f*******4 的大作中提到】
: 考虑前缀和的数组s[0..n]的下标a=s[b],那么如果s[b..c]满足均值: 么s[a...c]也一定满足,所以这里是单调的.
: 于是可以从左到右建严格递增的下标序列(用stack即可), answer的开始值肯定在这些
: 之中.
: 结束位置也类似,但只需维护一个最小且最右的下标即可.这样就是O(N)

avatar
w*s
15
这个解法应该是错的。
我这里提供一个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)

avatar
b*e
16
你这个和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最后一个元素比较,

avatar
b*e
17
牛逼。不得不出来顶一下。这个不容易想到。面试的时候谁能做出来这个那绝对是天人
合一。

【在 f*******4 的大作中提到】
: 考虑前缀和的数组s[0..n]的下标a=s[b],那么如果s[b..c]满足均值: 么s[a...c]也一定满足,所以这里是单调的.
: 于是可以从左到右建严格递增的下标序列(用stack即可), answer的开始值肯定在这些
: 之中.
: 结束位置也类似,但只需维护一个最小且最右的下标即可.这样就是O(N)

avatar
w*s
18
后半部分是一样的,前面的部分他没有转换,所以有点问题。

【在 b***e 的大作中提到】
: 你这个和fabregas4的解法是一模一样的。你说的更清晰一些罢了。
:
: ]
: 较,

avatar
z*6
19
这两个解法本质上是一样的,fabregas4还比westmites少个辅助数组b。
avatar
m*i
20
fabregas4的明显有问题。度没有用到小于k这个条件

【在 z******6 的大作中提到】
: 这两个解法本质上是一样的,fabregas4还比westmites少个辅助数组b。
avatar
m*i
21

]
较,
只和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最后一个元素比较,

avatar
w*s
22
确实是O(n),但是我之前没有想清楚最后扫描的时候修改c的方法,现在已经在原帖上修
正了。

【在 m******i 的大作中提到】
:
: ]
: 较,
: 只和c最后一个元素比较O(N)找出来的不是最长的。最长的估计要 O(NlgN)

avatar
x*a
23
这个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最后一个元素比较,

avatar
w*s
24
没看懂你啥意思,不过O(n)是对于数组有正有负都一样的。

【在 x*****a 的大作中提到】
: 这个O(n) 是建立在数组全部都是正数的情况下, 如果有正有负, 这个跟严格递增没有
: 关系, eg
: sum[i] = {-100, 1, -100, 2, -100, 3, -100, 4, 1, -1}
: 最长sub array就是用[0...n-1]
: 还是我理解有错?
:
: ]
: 较,

avatar
x*y
25
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这个条件
avatar
m*i
26
妙!大牛指教了!

上修

【在 w*******s 的大作中提到】
: 确实是O(n),但是我之前没有想清楚最后扫描的时候修改c的方法,现在已经在原帖上修
: 正了。

avatar
f*4
27
stack和最后元素x维护的都是下标. 所以判断时检查 (s[x]-s[stack.top()])/(x-
stack.top())和k的大小关系

【在 w*******s 的大作中提到】
: 后半部分是一样的,前面的部分他没有转换,所以有点问题。
avatar
w*s
28
我觉得是错的

【在 f*******4 的大作中提到】
: stack和最后元素x维护的都是下标. 所以判断时检查 (s[x]-s[stack.top()])/(x-
: stack.top())和k的大小关系

avatar
b*e
29
不必纠缠于细节。他的意思就是说求的是各点到y = kx的距离,而不是到y = 0的距离
。那个大方向上的思路是对的。

【在 w*******s 的大作中提到】
: 我觉得是错的
avatar
n*f
31
我觉得你的算法实际上是贪心法。递减点(右-左)减去最大点(左到右),不一定得
到最优解。

]
较,

【在 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最后一个元素比较,

avatar
n*f
32
“对于题目所求,我们希望s[i]越大越好,s[j + 1]越小越好,这样他们的差才会小”
我觉得这个不对。这样求出来的是平均值较小的,而不是满足条件的最长的subarray。
有时候,s[j+1+1]对应的数a[j+1](不是递减点),由于a[j+1]较小,但是跟前面的
suarray平均下,依旧满足条件。
愚见而已,还请大神们指点。
avatar
w*s
34
你没看懂,前面有人贴了leetcode的题解,你可以参考一下。

【在 n******f 的大作中提到】
: “对于题目所求,我们希望s[i]越大越好,s[j + 1]越小越好,这样他们的差才会小”
: 我觉得这个不对。这样求出来的是平均值较小的,而不是满足条件的最长的subarray。
: 有时候,s[j+1+1]对应的数a[j+1](不是递减点),由于a[j+1]较小,但是跟前面的
: suarray平均下,依旧满足条件。
: 愚见而已,还请大神们指点。

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。