找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 4414|回复: 20
收起左侧

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

  [复制链接]

8

主题

7

精华

475

积分

高级会员

Rank: 3Rank: 3

积分
475
发表于 12-1-2014 10:49 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
前几天在群里讨论一道题:给一个nxn的矩阵,元素是数字,求不超过某个数的最大子矩阵。
" j# r; k7 E& |) u+ g当时讨论的办法是枚举两条边,计算两条边之间的和,转化成一维的问题,问题就简化为:/ Z" i% B& T/ G. \3 @
给一个数组,求和不超过某个数的最大连续区间。6 {. h6 g/ l' e- R+ L- [2 W

  ]3 G# G! @+ @( A) |0 s8 r9 V若元素全是正数,可以用一个窗口滑动,根据窗口中元素之和与指定值的大小调整窗口,这个办法可以做到O(n)。& j; J. K( _4 ^
  1. int MaxRange1(const vector<int>& arr, int budget) {
    ( m+ e3 z/ @+ e0 G! x- G
  2.     int range = 0;
    . E3 T! n8 y7 U# h6 I/ ?7 ^% E
  3.     int i, j;
    2 @& Z$ X/ N9 {/ M; x
  4.     i = j = 0;
    - G. M/ i! g8 J
  5.     int sum = 0;
    4 v4 ~4 ~0 F1 s% R3 n! ]  j
  6.     int n = arr.size();! E0 p# P# O, B* \
  7.     while (j < n) {
    ( h$ M  N. M5 [; t! m) v
  8.         while (j<n && sum + arr[j] <= budget) {
    / X3 X+ O$ I+ Y, C# b
  9.             sum += arr[j];* K* [5 G9 r) T  F
  10.             ++j;
    9 W" w+ T9 o- u* |# s1 ?
  11.         }
    . I9 z- F' a, Z# b+ v2 [
  12.         range = std::max(range, j-i);0 T. `& N2 {6 {: E' g- ?" e
  13.         while (i<n && sum > budget) {
    + i" v" `8 U+ K) {
  14.             sum -= arr[i];; l/ l+ ?. n6 K& z# g( o& W
  15.             ++i;
    , c0 c) c6 W. p3 ~
  16.         }% a7 }, R# I$ l& x. i; F* Q5 f
  17.     }' g5 a5 P8 U* x
  18.     return range;: O; U& J% U4 X/ {, S4 o
  19. }
复制代码

* {, |0 \: |7 H' s$ m3 Y' \. A那么元素有正有负的情况呢,我当时在群里说,即便有正有负,也可以用一个窗口滑动。说这话时只是直觉上觉得可以。
% a3 [* J0 J7 e  _1 v下面记录一下当时的思考过程,也就是我当时想出这个办法的动机。: }3 y( b5 U: r
若元素有正有负,因为sum+arr[j]不一定一直变大,上面这种滑窗办法不能继续使用。需要寻找新的办法。先寻找连续区间和的简洁表示,连续区间的和可以表示成这个区间头尾前缀和的差。比如sum(i..j)=sum(0..j)-sum(0..i-1)。这个问题就可以转化成:给一个数组,求差值不超过某数的最大连续区间。
! w) a0 ^: D" h* o3 i8 [; n1 f) d( k同样从简单情况开始,如果都是正数,这个前缀和单调递增,可以把上面的代码稍微改动一下:" F5 V8 T7 S9 l
  1. int MaxRange2(const vector<int>& prefixSum, int budget) {
      A! }+ h! A& V" K* u- R3 Y) g
  2.     int range = 0;+ u* x2 d; D4 N9 \% r5 ]2 Q/ _5 r
  3.     int i = 0;0 n3 ]) X' s7 A6 d7 M
  4.     int j = 0;
    ( [2 `, K6 \1 u9 `* d4 ^; O# T
  5.     int sum = 0;
      ]: m* M1 D' _# I0 Q0 u# t0 F
  6.     int n = arr.size();( \: w& r+ S& }- i1 R' ~
  7.     while (j < n) {
    - i8 J" Z$ D9 b  R' P3 A5 f. L+ K
  8.         int pi = prefixSum[i];
    + |; M9 h$ p  i) h* w: e) g
  9.         while (j<n && prefixSum[j] <= pi + budget) {
    : L8 K- q# D2 u6 t3 B+ N. h7 r
  10.             ++j;5 k6 \" q% q; o
  11.         }: F! Z$ Q$ K) V8 G7 e4 w3 s! @; s
  12.         range = std::max(range, j-i-1);
    + C% w0 I7 B$ R5 S; A* O
  13.         while (i<n && prefixSum[i] <= pi) {: m  v1 g" N. X& F, _: ^1 ?( D
  14.             ++i;//由于prefixSum单调增,这个循环其实只跳过了相同大小的元素$ O  P) r1 x  m! x+ M2 T( K* u
  15.         }9 R. \5 J) I  o+ }" |
  16.     }
    " I! y% M) h1 E4 |: B& P
  17.     return range;
    6 t$ m( l  o% A9 l' N
  18. }
复制代码
6 c# ?6 ]! }! e2 Y' _1 s& U9 q

  Y9 [9 g7 P1 D" T" k而若数组中有正有负,那么即便prefixSum[j] <= pi + budget这个条件不成立,我们也不能退出,因为不知道前面更大的j是否会有更小的prefixSum[j]。也就是说,我们想要知道什么呢?j往后是否有更小的prefixSum[j]。这很容易啊,只要先从后往前预计算出每个(j..n-1)区间的最小值就可以了。- t! j1 R: O3 {- j
稍微改动一下代码就可以了。
7 z( L# \3 g; j( F) I1 C
  1. int MaxRange3(const vector<int>& prefixSum, int budget) {3 u1 x$ x- B: L1 \( m; O) G" ]
  2.     int n = prefixSum.size();! z* b8 Z+ u4 B2 M4 O8 i
  3.     if (n == 0) return 0;6 \7 o# H3 S0 t1 V8 C/ U3 T
  4.     vector<int> min(n);) O2 w( @# Z! r9 Q4 K  G
  5.     min[n-1] = prefixSum.back();$ I  e( U" }- x% C. @
  6.     for (int i = n-2; i >= 0; --i) {7 h" q, G4 `4 g1 \
  7.         min[i] = std::min(prefixSum[i], min[i+1]);
    # E+ J0 J% V* [' W" T
  8.     }
    ( K8 h" r- x2 A1 l4 f& t) }
  9.     int i = 0;/ }( W8 N0 G4 y+ {
  10.     int j = 0;$ E" U4 Y5 G4 u6 R' I( L
  11.     int range = 0;
    - C, N# Q- l4 W! w% B2 ^) s! \; A6 a6 R
  12.     //need to find the largest j such that prefixSum[j] <= prefixSum[i]+budget
    9 u6 B! x  v3 l. U) U5 Y, c
  13.     while (j < n) {, t+ y* K4 S! R! o! c: P* ~7 p
  14.         int pi = prefixSum[i];
    4 G; g8 w- `+ T
  15.         while (j < n && min[j] <= pi+budget) ++j;) T3 N+ S" m. p7 v
  16.         range = max(j-i-1, range);
    9 s7 t; k2 q' {3 v9 z3 v( W8 u
  17.         while (i < n && prefixSum[i] <= pi) ++i;
    # m  J$ K4 [7 k6 w4 [9 E, f2 c
  18.     }& t5 ~. `: h5 ~+ K. h2 g
  19.     return range;
    4 S$ l- C" x2 W; V5 W
  20. }
复制代码
+ x, u+ F9 P8 k5 e
后来曹神(@Javaman曹鹏)和孙神(@THU-研三-孙冕)都跟我说单调栈可以,这里把他们的想法整理一下(其实孙神的想法我还没完全理解,但我觉得应该是差不多的意思,只是对起点和终点都使用了栈)。
" q  b6 Y$ ^2 i! d前缀和数组,对每一个终点找一个起点,起点越老,值应该越大,否则对这个终点,可以用前面一个值更大的作为起点而区间更大。(上面第二个循环while (i < n && prefixSum <= pi) ++i;其实也是这个意思。)这就启发我们用一个单调栈,记录下所有的起点,起点从栈顶到栈底单增。再对前缀和数组从后往前看可能的终点。
7 [2 A4 f( l5 s) ~9 \( N& c
  1. int MaxRange4(const vector<int>& prefixSum, int budget) {0 ]  }* m, z7 D/ L9 H( R
  2.     stack<int> st;
    9 ^( m& Q2 ~" \& k' t0 J7 q- n
  3.     int n = prefixSum.size();
    ' [. p0 f) f+ p
  4.     if (n == 0) return 0;! R8 H! b7 f5 ~0 |, e& _! Y
  5.     st.push(0);
    2 H6 k1 A/ g6 X: w/ n8 u$ P
  6.     for (int i = 1; i < n; ++i) {) _) L9 x) C) G/ q8 B2 v6 Y
  7.         if (prefixSum[st.top()] < prefixSum[i]) {
    4 B& p3 J# b9 T8 `% @
  8.             st.push(i);+ ?5 C' h7 F9 \4 G
  9.         }
    7 Q- V" _. J, x! E' U1 A
  10.     }
    ; L* O4 ~' I5 t& |1 C" p  z2 x( C. f
  11.     int range = 0;
    1 D4 U& h9 R2 i6 y0 S0 p5 O
  12.     for (int i = n-1; i >= 0; --i) {
    4 L( ?# V) v) W1 S. H5 N( k
  13.         while (prefixSum[i] <= prefixSum[st.top()] + budget) {5 b* G) \+ [  y, F9 B
  14.             range = max(range, i-st.top());! ^  h: A. a2 t  {0 S7 D
  15.             st.pop();  M0 r' ?. M4 v8 k3 Y
  16.             if (st.empty()) break;  r6 m: }$ c9 Q3 }# c  [& }
  17.         }( I/ S" b  ?! s6 O$ Z8 \" E6 f! f
  18.     }, `: k8 f6 \! m+ U
  19.     return range;7 x9 ?: I3 q( m/ ]2 H6 C' E
  20. }
复制代码
上面对于包含正负数的情况,时间和空间复杂度都是O(n)。( n' ]% T3 g# |% Z
需要注意的细节:前缀和数组要预先放一个0,否则不能用这个办法计算包括开头元素的连续区间。
+ \  H2 y+ T1 z' y
& q/ L5 N5 y7 T( d  v
* t4 l* W$ _7 r2 n' E1 }- x补充内容 (12-1-2014 10:52 PM):
6 j5 B3 S3 N& {7 I8 n6 w. o; i改不了帖子了,while (i < n && prefixSum(i) <= pi) ++i;这里貌似把【i】理解成格式了,尽管没有对应的终结。以致于后面都变成了斜体。
- y1 b( d0 t/ C5 e/ Y* g  [. I+ m5 g2 E7 C2 |
补充内容 (12-2-2014 01:54 AM):
' R$ \* b1 n7 `# M8 q忘了说了,曹神指出这跟 http://leetcode.com/2011/05/a-distance-maximizing-problem.html 是类似的。
4 m6 e% [  N; s3 T3 I
/ P' c3 N2 h# E5 u0 S补充内容 (12-2-2014 09:17 PM):
/ u7 `  r8 F2 M- |第四段代码有bug,break错循环了。应该是下面这样。
! b6 m& X4 D" h+ Q. {int MaxRange4(const vector<int>& prefixSum, int budget) {
6 z& b! U/ H. }, ^3 _- J4 e    stack<int> st;7 f1 y- M9 @9 \2 y* ~
    int n = prefixSum.size();
+ d2 }4 f: r; k6 l    if (n == 0) return 0;
6 R, r$ C2 }6 c# @    st.push(0);% e6 D6 q9 h  O! u3 }1 J) c- G
    for (int i = 1; i < n; ++i) {* R7 K& K) C% j, c5 k+ q# ^
        if (prefixSum[st.top()] < prefixSum) {  {. B% q7 ?4 q
            st.push(i);6 Y& Z- Q* S7 o0 T5 V* O' l; ?
        }
5 `! A5 q& n) v7 }2 k' Q    }
3 ~2 e) W4 e, q9 |, P' m) K+ E    int range = 0;
, K; F  h. l# W' n( c; p    for (int i = n-1; i >= 0; --i) {
2 x7 D) G7 D8 y- n        while (!st.empty() && prefixSum <= prefixSum[st.top()] + budget) {
+ r/ U' Q2 n% }; X. V; L* ]/ z            range = max(range, i-st.top());
* o( N8 n, ~; V" O' h0 w2 x            st.pop();   
3 X# |/ h2 n" i% y* Q        }
% X- g% U  {& s0 ]+ J/ g/ K  L0 s. b        if (st.empty()) break;
8 @. K* X7 Z2 ^0 Y    }/ f+ q; P6 ?) n) G
    return range;. y6 h( X. E! i( \# i' b7 B
}, j7 P2 g8 i( C- F0 J
% |# P5 n3 M8 z5 s
补充内容 (2-3-2015 02:17 AM):4 P- ~: C1 c: }" Z' S1 W
kimi0428 pointed out a bug. I cannot enter more than 200 characters here. So I've corrected in the 20th thread. $ @2 n6 W2 ?1 n4 Y! b
http://www.meetqun.com/forum.php ... =2592&pid=42792/ b7 |$ R! m3 \/ m
Thanks kimi0428.
发表于 12-2-2014 01:02 AM | 显示全部楼层
加个精华。。。
发表于 12-2-2014 01:10 AM | 显示全部楼层
仔细读了下 应该起点越老 值越小吧。。。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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