找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

楼主: ridershen
收起左侧

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

  [复制链接]
发表于 12-3-2014 05:08 AM | 显示全部楼层
lambdai 发表于 12-3-2014 03:06 AM
  p7 }% J* B1 R1 \leetcode那道题可以只用一个栈,右端点j入栈的时候同时计算区间并同时把无效的i弹出去
. R4 e% N5 |5 G. Y' L- T5 ]5 g" p  c) O2 M& h( s2 y
lz这道好像不能 ...
* s; K* j7 m$ ]) e: F6 s
一个栈可以的 您理解应该有误
我们始终相信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
) O; m- g4 n: h一个栈可以的 您理解应该有误

' Q9 |5 n- F0 z5 U* z8 H想明白了,可以一个栈都不用。
$ u5 n8 v2 q+ V  n+ @; F" T预处理minprefixsum[j] := min(prefixsum[j], prefixsum[j+1]...prefixsum[n]), 这个数组是非严格的单调增
. t" E3 p2 J. E左边的从prefixsum[i=0]开始,只考虑比prefix[0..i-1]都大的i, : _; @( W( v1 O3 Q" v1 j6 k% ^! W
对每个考虑的i, 右端点j从上次的j开始(开始是0)往右撸直到minprefixsum[j] - prefixsum > target
* @7 A* b4 z. `% |! V找到对应的j后尝试更新最大的j-i
" {* d0 P  q; c$ I# R0 H5 t因为搜索的时候i 和 j 都在增大,所以O(N)* L0 z0 I1 D: d0 ]3 `4 }

, N0 m8 y) p. B  M! j$ h  Y  I3 v看了一下lz的原始不用栈的代码,除了lz是给右端点j找左端点i,应该是基本一样的8 y9 p; q9 ~1 ^+ m* l- c
/ }( J5 p7 ?7 K
多谢lz和cpcs
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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