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

ridershen

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

5 x9 A6 e& U1 w& y* q起点越老，这个老字，我理解是作为起点的index越大。不知道跟您说的老是不是一个概念。
/ l$ ~, ?* v( M8 ?您说的这个情况，比如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]。
! R. n1 g* N* ~
3 e7 G& l: F" l% P: L1 E
2 Z" g+ b2 a! Z* H% {# f% b补充内容 (12-2-2014 02:02 AM):
8 x3 y6 @0 T' q: \orz,这里面prefixSum，应该是prefixSum(i)，那个中括号加i又被当成格式了

codingcodingcod

先 mark         

lambdai

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

! c4 D# \( [, |8 ?- }leetcode那道题可以只用一个栈，右端点j入栈的时候同时计算区间[i-j]并同时把无效的i弹出去
; W& F6 P3 c4 A0 y+ X4 B* W
" ^4 |( i" K# Qlz这道好像不能只用一个栈，要有一个左端点栈和一个右端点栈
3 W' l) A4 }6 O( y
@cpcs 我理解得对吗?