|
|
发表于 12-3-2014 09:41 PM
|
显示全部楼层
3 B2 X. H7 t( r想明白了，可以一个栈都不用。& m/ I% h: v7 s1 _
预处理minprefixsum[j] := min(prefixsum[j], prefixsum[j+1]...prefixsum[n])， 这个数组是非严格的单调增$ F* W) J0 N, y1 r3 R; g3 e
左边的从prefixsum[i=0]开始，只考虑比prefix[0..i-1]都大的i, , a1 L( `/ ]# {9 b g, t
对每个考虑的i, 右端点j从上次的j开始(开始是0)往右撸直到minprefixsum[j] - prefixsum > target! `+ L. }8 ^ B2 U
找到对应的j后尝试更新最大的j-i0 j( J! e# a9 y2 G' e) X3 i% V
因为搜索的时候i 和 j 都在增大，所以O(N)- c0 @; ?/ R9 ?9 ]' q; P' H. e. {
4 {5 \+ t6 _4 W4 W g! t) I- C
看了一下lz的原始不用栈的代码，除了lz是给右端点j找左端点i，应该是基本一样的
. L+ O) z1 l4 ~3 x$ E1 f9 N' `( A* y$ J- _
多谢lz和cpcs |
|
楼主: ridershen
[复制链接]
发表于 12-3-2014 05:08 AM
发表于 12-3-2014 05:25 AM
