一道算法題的一種O(n)解法

2019-11-17 03:49:27

字體：大中小

供稿：網(wǎng)友

很早就有去做做的想法，可是一直沒動手

今天花了點(diǎn)時間搞搞

結(jié)果如下：

核心部分

代碼
1  public List<Result> GetResults(int[] arr)
2         {
3             //輸入有效性檢測
4             if (arr.Length==0)
5                 throw new NotEnoughInputException();
6
7             List<Result> rlist = new List<Result>();
8
9             //實(shí)際運(yùn)算
10
11             //初始化起始位置，將第一點(diǎn)當(dāng)作后續(xù)結(jié)果的起點(diǎn)
12             Position startP = new Position(Position.EmptyPosition, arr[0]);
13
14             //當(dāng)前點(diǎn)就當(dāng)作是最大結(jié)果值
15             Result curResult = new Result(Position.EmptyPosition, startP);
16
17             //向結(jié)果列表添加內(nèi)容
18             rlist.Add(curResult);
19
20             //有一個以上的數(shù)據(jù)
21             if (arr.Length > 1)
22             {
23                 Position curP,nextP;
24                 curP=startP;
25                 Result temp;//保存到目前點(diǎn)為止的結(jié)果數(shù)據(jù)
26                 //從第二個點(diǎn)開始逐個判斷
27                 for (int i = 1; i < arr.Length; i++)
28                 {
29                     //構(gòu)造對象
30                     nextP = new Position(curP,arr[i]);
31                     temp = new Result(startP, nextP);
32
33                     //判斷當(dāng)前的和是否大于現(xiàn)有結(jié)果列表中的數(shù)據(jù)
34                     if (temp.RelativeElevation > rlist[0].RelativeElevation)
35                     {//如果大于則清除結(jié)果列表，添加當(dāng)前結(jié)果
36                         rlist.Clear();
37                         rlist.Add(temp);
38                     }
39                     //判斷當(dāng)前的和是否等于現(xiàn)有結(jié)果列表中的數(shù)據(jù)
40                     else if (temp.RelativeElevation == rlist[0].RelativeElevation)
41                     {
42                         rlist.Add(temp);
43                     }
44                     //判斷當(dāng)前是否是一個新的低點(diǎn)
45                     else if(nextP.EndElevation<=startP.StartElevation)
46                     {
47                         startP = nextP;
48                     }
49                     curP = nextP;
50                 }
51             }
52
53             return rlist;
54         }

代碼還有進(jìn)一步優(yōu)化的余地

主體思想就是模擬一個不斷爬山的人，爬完一遍后要回答那座山和山谷的相對落差最大

完整代碼在此

主要多用了些類，呵呵。

局部代碼有些不好理解，呵呵。比如里面關(guān)于全負(fù)數(shù)的處理。

歡迎拍磚

上一篇：網(wǎng)盤工具比較,以及自己開發(fā)的網(wǎng)盤工具

下一篇：ASPX 的 @Register 命令