一道算法題的一種O(n)解法
2019-11-17 03:49:27
供稿：網友
很早就有去做做的想法，可是一直沒動手
今天花了點時間搞搞
結果如下：
核心部分
代碼
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 //實際運算
10
11 //初始化起始位置，將第一點當作后續結果的起點
12 Position startP = new Position(Position.EmptyPosition, arr[0]);
13
14 //當前點就當作是最大結果值
15 Result curResult = new Result(Position.EmptyPosition, startP);
16
17 //向結果列表添加內容
18 rlist.Add(curResult);
19
20 //有一個以上的數據
21 if (arr.Length > 1)
22 {
23 Position curP,nextP;
24 curP=startP;
25 Result temp;//保存到目前點為止的結果數據
26 //從第二個點開始逐個判斷
27 for (int i = 1; i < arr.Length; i++)
28 {
29 //構造對象
30 nextP = new Position(curP,arr[i]);
31 temp = new Result(startP, nextP);
32
33 //判斷當前的和是否大于現有結果列表中的數據
34 if (temp.RelativeElevation > rlist[0].RelativeElevation)
35 {//如果大于則清除結果列表，添加當前結果
36 rlist.Clear();
37 rlist.Add(temp);
38 }
39 //判斷當前的和是否等于現有結果列表中的數據
40 else if (temp.RelativeElevation == rlist[0].RelativeElevation)
41 {
42 rlist.Add(temp);
43 }
44 //判斷當前是否是一個新的低點
45 else if(nextP.EndElevation<=startP.StartElevation)
46 {
47 startP = nextP;
48 }
49 curP = nextP;
50 }
51 }
52
53 return rlist;
54 }
代碼還有進一步優化的余地
主體思想就是模擬一個不斷爬山的人，爬完一遍后要回答那座山和山谷的相對落差最大
完整代碼在此
主要多用了些類，呵呵。
局部代碼有些不好理解，呵呵。比如里面關于全負數的處理。
歡迎拍磚
