用脸贴着问题想问题

—

由

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

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

比如下面这个小问题：

某股票价格，一定时间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] )

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

（该时间点价格－当前最小价格）或（之前保存的最大价格差）

评论