用脸贴着问题想问题

平时喜欢站在高处俯看问题,觉得很自在,有种掌控全局的感觉。比如画流程图解决某个功能性问题,一目了然,没有技术难点的话,基本一下子就能解决问题。

但有时候有必要试着放低身板,并肩站在问题身旁寻求解决办法。身在山中也无妨,由小而大,从局部推至整体,有时候可以更好的解决问题。

比如下面这个小问题:

某股票价格,一定时间t内价格变化为P1, P2, P3, …, Pn. 则不同时间点的价格差为P_{j}-P_{i} ( 时间点 j > 时间点 i ). 求这段时间t内的最大价格差。(n >= 500000, 1 <= P_{i} <= 10^{9} )

从整体看,会很容易想出把每个差求一遍,最后得出最大差值:(maxV: 当前最大价格差,max: 求两者间较大者,min: 求两者间较小者)

for j ( 1 ~ n-1 )
  for i ( 0 ~ j-1 )
    maxV = max ( maxV, P[j]-P[i] )

这样可以解决问题,但效率不行,n比较大,双循环会很慢。

此时把眼光聚焦到每个时间点,从时间点0开始思考,然后依次推向最后时间点n,会发现一次循环便可以解决问题:(maxV: 当前最大价格差,minP: 当前最小价格,max: 求两者间较大者, min: 求两者间较小者)

minV = P[0]
for j ( 1 ~ n-1 )
  maxV = max ( maxV, P[j]-minP )
  minP = min ( minP, P[j] )

即,从任何一个时间点往回看的话,该时间点的最大价格差就是:

该时间点价格 - 当前最小价格) 或 (之前保存的最大价格差