找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

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

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

  [复制链接]

8

主题

7

精华

475

积分

高级会员

Rank: 3Rank: 3

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

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

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

x
前几天在群里讨论一道题:给一个nxn的矩阵,元素是数字,求不超过某个数的最大子矩阵。
) P9 L2 w3 A3 H! V0 m/ j  V5 o当时讨论的办法是枚举两条边,计算两条边之间的和,转化成一维的问题,问题就简化为:: v1 g( R% j8 k6 X+ j
给一个数组,求和不超过某个数的最大连续区间。) ]; f1 l3 X1 T; M, B+ r$ E
( u- ~$ I  e3 E" M
若元素全是正数,可以用一个窗口滑动,根据窗口中元素之和与指定值的大小调整窗口,这个办法可以做到O(n)。
( V. v* P6 h. y3 Q0 |) m. o
  1. int MaxRange1(const vector<int>& arr, int budget) {+ Z+ g  i9 N3 `: h
  2.     int range = 0;$ R* @. s# d, J$ U6 Q, N4 N* G
  3.     int i, j;
    9 f  i/ @; [) o3 D- Q
  4.     i = j = 0;9 K) f2 g/ C3 L
  5.     int sum = 0;6 ]- v4 b$ H$ k' l% p5 J: t8 }
  6.     int n = arr.size();0 r, V$ }) Q! a( m
  7.     while (j < n) {3 {; l# S6 ?! e) |" U& F
  8.         while (j<n && sum + arr[j] <= budget) {
    2 K. [$ N' X( ~0 T
  9.             sum += arr[j];5 A7 f) E% t% S( O* T
  10.             ++j;
    ' ]+ j1 n) |" o& G3 h; g9 c
  11.         }* y6 V+ z! w, I! J$ @1 m# W. u' a
  12.         range = std::max(range, j-i);( `2 Z% {7 t1 G  L5 v' A
  13.         while (i<n && sum > budget) {' N9 k" C3 u2 x. T" a9 o
  14.             sum -= arr[i];6 ?6 H: |. K2 W% [/ Q1 N; L9 H* p0 ]
  15.             ++i;
    & A/ r; Z; g8 @  W4 R
  16.         }8 O  I% n& M  r8 E( o6 R
  17.     }: l( D+ t$ \% v9 _$ n  o
  18.     return range;
    8 j+ {' R: O. f) y
  19. }
复制代码

; h* R; N& j! h* ^, \2 _那么元素有正有负的情况呢,我当时在群里说,即便有正有负,也可以用一个窗口滑动。说这话时只是直觉上觉得可以。
/ ^. {' D4 C, b下面记录一下当时的思考过程,也就是我当时想出这个办法的动机。  ~4 ]8 A% `( N3 ?
若元素有正有负,因为sum+arr[j]不一定一直变大,上面这种滑窗办法不能继续使用。需要寻找新的办法。先寻找连续区间和的简洁表示,连续区间的和可以表示成这个区间头尾前缀和的差。比如sum(i..j)=sum(0..j)-sum(0..i-1)。这个问题就可以转化成:给一个数组,求差值不超过某数的最大连续区间。' J* m# p; B& F% p  h9 j( n
同样从简单情况开始,如果都是正数,这个前缀和单调递增,可以把上面的代码稍微改动一下:& K; C4 w% q* E: D5 B/ ?
  1. int MaxRange2(const vector<int>& prefixSum, int budget) {  j2 X3 _; ]2 f/ r3 h2 `, @  |; a
  2.     int range = 0;
    ' q3 T7 o: }( z7 Y0 r
  3.     int i = 0;
    0 w1 Z" c. J0 }7 Y$ t- P
  4.     int j = 0;0 ]2 a: e0 d3 a( x: v
  5.     int sum = 0;
    0 \; I' V2 [5 x8 K5 A& N
  6.     int n = arr.size();
    6 Y# J# |% J/ S: K- V
  7.     while (j < n) {7 j8 A5 v% s( ^+ r2 r2 a
  8.         int pi = prefixSum[i];6 t4 F- g6 ]+ r% g- i
  9.         while (j<n && prefixSum[j] <= pi + budget) {3 R' u; @, {4 ]9 p8 \
  10.             ++j;
    * n/ J5 y2 v; z+ @) t! ^5 Z
  11.         }8 P0 k1 r. _% m* j+ Y
  12.         range = std::max(range, j-i-1);' A4 ^% g- P5 T
  13.         while (i<n && prefixSum[i] <= pi) {/ ^4 G6 p2 M/ Q  h% R' u; M- F3 a
  14.             ++i;//由于prefixSum单调增,这个循环其实只跳过了相同大小的元素0 h% ^+ U& ]. E
  15.         }
    " C5 g# H; Z) o8 `( w* p" _* m
  16.     }
    * i: i4 t( z$ @& g# n1 h' R  V
  17.     return range;' V$ s, j' }( x4 @
  18. }
复制代码

; K* j' E# B6 D- q$ T
, v  v, A* X! K2 H  u而若数组中有正有负,那么即便prefixSum[j] <= pi + budget这个条件不成立,我们也不能退出,因为不知道前面更大的j是否会有更小的prefixSum[j]。也就是说,我们想要知道什么呢?j往后是否有更小的prefixSum[j]。这很容易啊,只要先从后往前预计算出每个(j..n-1)区间的最小值就可以了。
' W% b  U; B: e& T8 J$ M: ], L0 S稍微改动一下代码就可以了。
: o8 U" }2 U1 K3 d( V! d5 A3 x8 X
  1. int MaxRange3(const vector<int>& prefixSum, int budget) {
    3 T1 m/ S5 r5 G9 q; u! C
  2.     int n = prefixSum.size();
    5 X' o2 E& F5 _8 l4 J2 Y) u1 Q
  3.     if (n == 0) return 0;  u- b2 K) L# B
  4.     vector<int> min(n);& _+ |) H( }- y& b, i
  5.     min[n-1] = prefixSum.back();
    6 S7 c+ K+ \: |
  6.     for (int i = n-2; i >= 0; --i) {
    . T3 M$ n" F1 ], F( S( f
  7.         min[i] = std::min(prefixSum[i], min[i+1]);
      [; ^. x3 R; ], @. q5 F
  8.     }
    ; J# y0 k* [/ h' W: u! G% v
  9.     int i = 0;& M: ]. [4 m! h7 M* q
  10.     int j = 0;: @  q: Z6 u! _( _; \1 l
  11.     int range = 0;
    ; v0 `# k$ J# S  t& W
  12.     //need to find the largest j such that prefixSum[j] <= prefixSum[i]+budget
    ) I7 [0 j' b0 {8 U, }! @4 o
  13.     while (j < n) {8 {9 B( j( M2 r% A' I2 T
  14.         int pi = prefixSum[i];
    $ q% D6 j; v2 _; D% d
  15.         while (j < n && min[j] <= pi+budget) ++j;9 ?% n1 V# i$ q. C) D
  16.         range = max(j-i-1, range);
    9 f2 p2 K' I3 \, O2 ~7 W- h  }( j
  17.         while (i < n && prefixSum[i] <= pi) ++i;7 l4 T% j/ G- U! `6 a& L
  18.     }
      S" d$ o4 u9 m' X  d2 \
  19.     return range;
    3 l0 t' J2 j" Q6 p
  20. }
复制代码
8 i3 \6 X6 i5 }+ E& w! y) |4 {
后来曹神(@Javaman曹鹏)和孙神(@THU-研三-孙冕)都跟我说单调栈可以,这里把他们的想法整理一下(其实孙神的想法我还没完全理解,但我觉得应该是差不多的意思,只是对起点和终点都使用了栈)。
6 W5 C3 Y# H; `7 A2 w& W% y0 s前缀和数组,对每一个终点找一个起点,起点越老,值应该越大,否则对这个终点,可以用前面一个值更大的作为起点而区间更大。(上面第二个循环while (i < n && prefixSum <= pi) ++i;其实也是这个意思。)这就启发我们用一个单调栈,记录下所有的起点,起点从栈顶到栈底单增。再对前缀和数组从后往前看可能的终点。
6 |. }3 n2 G6 I5 A
  1. int MaxRange4(const vector<int>& prefixSum, int budget) {
    # |. {. Z- H5 O
  2.     stack<int> st;$ Q6 \4 ~! |' u1 Y( ]
  3.     int n = prefixSum.size();" l; t2 j) y) S: y
  4.     if (n == 0) return 0;, X0 |8 E' o% v! H
  5.     st.push(0);
    1 O3 z8 z. a% z6 D9 S, t8 e
  6.     for (int i = 1; i < n; ++i) {
    ' D. p0 M1 Q+ O7 z# [- {! R
  7.         if (prefixSum[st.top()] < prefixSum[i]) {% n3 E# S, g" j  N% ]" N8 t
  8.             st.push(i);% ^. `: |$ Z* P6 _9 O2 |* C
  9.         }& B9 W3 V' a. L
  10.     }
    " E4 C  |) q; h8 m
  11.     int range = 0;
    7 ~+ T0 k2 D. E: t5 I: [, t8 k
  12.     for (int i = n-1; i >= 0; --i) {9 `6 X, d& {7 b+ F- A5 }# Y3 g
  13.         while (prefixSum[i] <= prefixSum[st.top()] + budget) {0 z) C2 T+ e$ L1 \0 Y" m  D" ^6 |* P
  14.             range = max(range, i-st.top());5 V: L9 U$ h0 J; u9 Z
  15.             st.pop();5 Y- Y& {6 Z% v* ]" w9 U
  16.             if (st.empty()) break;; \# }9 s' v! e% b  ?4 ^8 P
  17.         }
    & B" B+ n+ l2 Y/ X5 L8 ?: u
  18.     }
    - N- v7 P: g) ]4 r
  19.     return range;& C3 V  `+ P2 S7 K6 Y
  20. }
复制代码
上面对于包含正负数的情况,时间和空间复杂度都是O(n)。" O. g$ g0 c/ D& q( s! d  f' j
需要注意的细节:前缀和数组要预先放一个0,否则不能用这个办法计算包括开头元素的连续区间。' X/ n4 }/ O8 L* T% P8 }3 W2 |9 Z

& N$ [% k1 P+ H' K% E
4 x5 G' K8 m( n- S1 s: U# E补充内容 (12-1-2014 10:52 PM):" O" |/ m  I0 u
改不了帖子了,while (i < n && prefixSum(i) <= pi) ++i;这里貌似把【i】理解成格式了,尽管没有对应的终结。以致于后面都变成了斜体。* Y5 F* r! x3 Q

& A# Y* C2 ^( I8 f$ c7 q, e补充内容 (12-2-2014 01:54 AM):% w, T: u0 e+ K- ?
忘了说了,曹神指出这跟 http://leetcode.com/2011/05/a-distance-maximizing-problem.html 是类似的。
  C/ C  K/ N9 G* p: g& a
# b6 P0 B; E. {% X, ~补充内容 (12-2-2014 09:17 PM):
8 ^( T( p* k) b. T9 F1 S: ~第四段代码有bug,break错循环了。应该是下面这样。0 T; k0 k. q$ F5 H6 u. [
int MaxRange4(const vector<int>& prefixSum, int budget) {0 u: C( W! @+ Z3 ]  Z, }6 J
    stack<int> st;( s  d) ?! ~& G4 Z
    int n = prefixSum.size();
- \7 s! A1 x# D    if (n == 0) return 0;& |; V; c. P) y0 Q
    st.push(0);% U0 `" o5 d$ {0 q+ L- _: U0 w
    for (int i = 1; i < n; ++i) {
9 a( h6 S: u  b: c4 s1 _: O5 x. A        if (prefixSum[st.top()] < prefixSum) {6 o. r! Y$ c: I+ i1 r; u' f
            st.push(i);
1 A- V$ }! Z( j' ~4 I( `5 {        }
$ ~2 d; Q% f& H' K! Y7 J    }) s/ L) |8 a, t, B( |
    int range = 0;
1 ~: o$ R2 e+ [: q+ @2 ]    for (int i = n-1; i >= 0; --i) {
5 U- w5 T6 U8 W2 t& b; U+ O8 m        while (!st.empty() && prefixSum <= prefixSum[st.top()] + budget) {
) h9 K; B8 R& m' ~+ ~% ]* m            range = max(range, i-st.top());
7 i2 N0 Q: U4 `9 \: c% R. x            st.pop();    ) @4 W  ?5 s! o) w' r
        }
* m, C' \3 C5 ?, |6 v0 T: T        if (st.empty()) break;
  _: E; P$ m  B8 o    }
" C0 ?7 W0 \, {    return range;
% x+ Q8 Q7 v1 ?2 v8 N7 i}) H* f- Y! k" X7 A1 a! M
6 R3 N8 ?9 \+ R
补充内容 (2-3-2015 02:17 AM):! `# U* G: [, q( @
kimi0428 pointed out a bug. I cannot enter more than 200 characters here. So I've corrected in the 20th thread. * I# t5 {' V7 x( r# n( u
http://www.meetqun.com/forum.php ... =2592&pid=42792/ e  C' e! L$ x  B
Thanks kimi0428.
发表于 12-2-2014 01:02 AM | 显示全部楼层
加个精华。。。
发表于 12-2-2014 01:10 AM | 显示全部楼层
仔细读了下 应该起点越老 值越小吧。。。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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