找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

楼主: ridershen
收起左侧

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

  [复制链接]

8

主题

7

精华

475

积分

高级会员

Rank: 3Rank: 3

积分
475
 楼主| 发表于 12-2-2014 02:01 AM | 显示全部楼层
cpcs 发表于 12-2-2014 01:10 AM( l4 }& \7 W5 I, ~6 X6 p9 t$ H
仔细读了下 应该起点越老 值越小吧。。。

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又被当成格式了

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 AM7 w! d/ w" P0 X! `3 }" l
其实您写的这个 就是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" T7 M% l- ^+ d+ \$ ^  U. M; l
@cpcs 我理解得对吗?
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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