找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

楼主: ridershen
收起左侧

[面经总结] 数组中和不超过某个数的最大连续区间

  [复制链接]

8

主题

7

精华

475

积分

高级会员

Rank: 3Rank: 3

积分
475
 楼主| 发表于 12-2-2014 02:01 AM | 显示全部楼层
cpcs 发表于 12-2-2014 01:10 AM: R% u4 a+ s& a& M
仔细读了下 应该起点越老 值越小吧。。。
. Q+ R8 F; v9 p3 q4 P! v' A2 f
起点越老,这个老字,我理解是作为起点的index越大。不知道跟您说的老是不是一个概念。' I( h' `6 l! `: Q) Z
您说的这个情况,比如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( e0 ~8 w" O/ a+ h

6 _) y, D- r3 A+ C0 s% h补充内容 (12-2-2014 02:02 AM):* p5 i3 ~3 F4 z, g1 ^, h1 T
orz,这里面prefixSum,应该是prefixSum(i),那个中括号加i又被当成格式了

0

主题

0

精华

206

积分

高级会员

Rank: 3Rank: 3

积分
206
发表于 12-2-2014 02:18 AM | 显示全部楼层
先 mark         

0

主题

0

精华

232

积分

高级会员

Rank: 3Rank: 3

积分
232
发表于 12-3-2014 03:06 AM | 显示全部楼层
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弹出去( A6 _: g( x6 t# m* {" L( P, V" @
4 K* b$ L7 V  J+ o! V5 t5 [7 Z. {0 g
lz这道好像不能只用一个栈,要有一个左端点栈和一个右端点栈
* C8 |& r3 N: g5 e$ b$ t! M4 T# w9 V1 L5 c- a! q
@cpcs 我理解得对吗?
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表