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

ridershen

cpcs 发表于 12-2-2014 01:10 AM
仔细读了下 应该起点越老 值越小吧。。。

起点越老，这个老字，我理解是作为起点的index越大。不知道跟您说的老是不是一个概念。
您说的这个情况，比如i<j, 如果prefixSum>=prefixSUm[j], 并且终点为k,prefixSum[k] <= prefixSum[j]+budget, 那么prefixSum[k] <= prefixSum[j]+budget<=prefixSum+budget, 这个j其实是没用的，因为i到k的区间更大。只需要保留i就行了。所以i<j，只需要考虑prefixSum < prefixSum[j]。
; k! s2 ?' K7 Q! s) u$ d

6 _) y, D- r3 A+ C0 s% h补充内容 (12-2-2014 02:02 AM):
orz,这里面prefixSum，应该是prefixSum(i)，那个中括号加i又被当成格式了

codingcodingcod

先 mark         

lambdai

cpcs 发表于 12-2-2014 01:21 AM
  |# g  `# d( ?' d( K其实您写的这个 就是max(j - i)那个题了。。。主要观点是 左端点左边必须都比它小 放堆栈里。右端点往左移 ...

  f& {4 a. B: z* W% `leetcode那道题可以只用一个栈，右端点j入栈的时候同时计算区间[i-j]并同时把无效的i弹出去

lz这道好像不能只用一个栈，要有一个左端点栈和一个右端点栈
* C8 |& r3 N: g5 e
@cpcs 我理解得对吗?