找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

楼主: ridershen
收起左侧

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

  [复制链接]
发表于 12-3-2014 05:08 AM | 显示全部楼层
lambdai 发表于 12-3-2014 03:06 AM
6 k0 F! H0 J% ^" s. G5 Dleetcode那道题可以只用一个栈,右端点j入栈的时候同时计算区间并同时把无效的i弹出去7 T. R' m# r0 M% y; H& w! B

, t% R8 ]' P2 G* V9 olz这道好像不能 ...

- `. A* @# j$ T- k' `+ w一个栈可以的 您理解应该有误
我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!

11

主题

0

精华

54

积分

资深会员

Rank: 2

积分
54
发表于 12-3-2014 05:25 AM | 显示全部楼层
先点赞!多谢!

0

主题

0

精华

232

积分

高级会员

Rank: 3Rank: 3

积分
232
发表于 12-3-2014 09:41 PM | 显示全部楼层
cpcs 发表于 12-3-2014 05:08 AM
; f5 n* \" u2 i4 [一个栈可以的 您理解应该有误

3 B2 X. H7 t( r想明白了,可以一个栈都不用。& m/ I% h: v7 s1 _
预处理minprefixsum[j] := min(prefixsum[j], prefixsum[j+1]...prefixsum[n]), 这个数组是非严格的单调增$ F* W) J0 N, y1 r3 R; g3 e
左边的从prefixsum[i=0]开始,只考虑比prefix[0..i-1]都大的i, , a1 L( `/ ]# {9 b  g, t
对每个考虑的i, 右端点j从上次的j开始(开始是0)往右撸直到minprefixsum[j] - prefixsum > target! `+ L. }8 ^  B2 U
找到对应的j后尝试更新最大的j-i0 j( J! e# a9 y2 G' e) X3 i% V
因为搜索的时候i 和 j 都在增大,所以O(N)- c0 @; ?/ R9 ?9 ]' q; P' H. e. {
4 {5 \+ t6 _4 W4 W  g! t) I- C
看了一下lz的原始不用栈的代码,除了lz是给右端点j找左端点i,应该是基本一样的
. L+ O) z1 l4 ~3 x$ E1 f9 N' `( A* y$ J- _
多谢lz和cpcs
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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