数组中和不超过某个数的最大连续区间

cpcs

lambdai 发表于 12-3-2014 03:06 AM
  p7 }% J* B1 R1 \leetcode那道题可以只用一个栈，右端点j入栈的时候同时计算区间并同时把无效的i弹出去
. R4 e% N5 |5 G. Y' L- T5 ]5 g
lz这道好像不能 ...

一个栈可以的 您理解应该有误

wkwan

先点赞！多谢！

lambdai

cpcs 发表于 12-3-2014 05:08 AM
) O; m- g4 n: h一个栈可以的 您理解应该有误

' Q9 |5 n- F0 z5 U* z8 H想明白了，可以一个栈都不用。
$ u5 n8 v2 q+ V  n+ @; F" T预处理minprefixsum[j] := min(prefixsum[j], prefixsum[j+1]...prefixsum[n])， 这个数组是非严格的单调增
. t" E3 p2 J. E左边的从prefixsum[i=0]开始，只考虑比prefix[0..i-1]都大的i,
对每个考虑的i, 右端点j从上次的j开始(开始是0)往右撸直到minprefixsum[j] - prefixsum > target
* @7 A* b4 z. `% |! V找到对应的j后尝试更新最大的j-i
" {* d0 P  q; c$ I# R0 H5 t因为搜索的时候i 和 j 都在增大，所以O(N)

, N0 m8 y) p. B  M! j$ h  Y  I3 v看了一下lz的原始不用栈的代码，除了lz是给右端点j找左端点i，应该是基本一样的

多谢lz和cpcs