1. 简介
在开发中，我们会遇到需要将数组转变成相邻关系的情况，这个过程就是将一个一维的数组，转化成一个有序的、带有某种相邻关系的形态。这个相邻关系可以是类似于树的结构，也可以是线性的有序关系。
Python提供了不同的构造方式来还原原来的数组和这个相邻关系。其中单向构造和双向构造是两种较常用的。
2. 单向构造
2.1 定义
单向构造是一种从前到后的构造方式，这个过程就是从第1个元素开始，经过一些规则依次构造当前元素到下一个元素的连边关系，直到数组结束。这种方式不会考虑后面的元素，只会考虑前面的元素。
2.2 实现原理
单向构造的实现可以基于一个简单的循环，遍历数组并在每个位置处处理一个元素，用它与之前的元素建立相邻关系，具体处理方法根据实际情况而定。例如，如果我们想要一个形成关于相邻温度的关系，我们可以使用下面的方法实现：
def construct_adj_arr(temp_arr):
n = len(temp_arr)
adj_arr = [[] for _ in range(n)]
for i in range(1, n):
for j in range(i):
if temp_arr[i] > temp_arr[j]:
strength = temp_arr[i] - temp_arr[j]
if strength > 4:
strength = 4
adj_arr[j].append((i, strength))
return adj_arr
上面的代码中，我们首先创建了一个空的、和原始数组长度一样的数组adj_arr，接着遍历原始数组temp_arr，并从第二个元素开始（索引为1）。对于每个新的元素temp_arr[i]，我们在之前的元素temp_arr[0:i-1]中找到所有小于它的元素temp_arr[j]，对它们之间建立一条相邻边(j, i)。这条边的强度strength是由2个元素之间的温度差决定的，强度的大小与温度差的大小成正比，如果温度差大于4，那么最大强度就是4。最后返回adj_arr。
2.3 测试
我们使用下面的示例测试单向构造：
temp_arr = [20, 24, 22, 25, 27, 23, 21, 19, 18]
adj_arr = construct_adj_arr(temp_arr)
for i, j_w in enumerate(adj_arr):
print(f"{temp_arr[i]:>5}:", end="")
for j, w in j_w:
print(f"({temp_arr[j]}:{w})", end="")
print()
输出结果为：
20:(24:3)
24:
22:(25:3)(27:4)
25:(27:2)
27:
23:(25:2)(27:3)
21:(25:4)(27:4)
19:(25:4)(27:4)
18:(25:4)(27:4)
输出每个元素和其它元素之间的关系，左侧数字是元素的值，右侧是它和其它元素的相邻关系，每个相邻关系是一个元组 (j, w)，表示元素j与它之间有一条连边，权重为w。
例如，第2行的24没有右侧相邻关系，这表示24没有大于它的元素；第3行的22有2个右侧相邻关系，表示22和25、27之间都有一条连边，权重分别为3和4；最后一行的18和它右侧的元素25、27之间都有连边，权重都为4。
3. 双向构造
3.1 定义
双向构造是一种从两端向中间的构造方式，这个过程就是从数组的两端（左端和右端）开始，根据一些规则依次构造左端元素到右端元素之间的连边关系，当左右端元素有交集时结束。这种方式通过考虑左右两端元素之间的关系来处理每个元素之间的连接关系，不仅考虑了左侧元素，还考虑了右侧元素。
3.2 实现原理
双向构造的实现包括两个主要部分，第一个部分找到数组的左右两端，第二个部分则是在左右端之间构造关系。例如要用它来处理相邻关系，我们可以采用下面的实现方式：
def construct_adj_arr(temp_arr):
n = len(temp_arr)
adj_arr = [[] for _ in range(n)]
left, right = 0, n-1
left_max, right_max = temp_arr[left], temp_arr[right]
while left < right:
if temp_arr[left] >= left_max:
left_max = temp_arr[left]
left += 1
elif temp_arr[right] >= right_max:
right_max = temp_arr[right]
right -= 1
else:
if left_max >= right_max:
strength = left_max - temp_arr[left]
if strength > 4:
strength = 4
adj_arr[left].append((right, strength))
left += 1
else:
strength = right_max - temp_arr[right]
if strength > 4:
strength = 4
adj_arr[right].append((left, strength))
right -= 1
return adj_arr
上面的代码首先创建一个空的、和原始数组长度一样的数组adj_arr，接着初始化左右端点的位置和当前位置的最大值。在while循环中，我们不断根据左右两端的元素，更新左右端点的位置和当前位置的最大值。如果当前的左侧元素大于或者等于之前的左侧元素的最大值，我们更新左侧元素的最大值，移动左端点。如果当前的右侧元素大于或者等于之前的右侧元素的最大值，我们更新右侧元素的最大值，移动右端点。如果左右两侧的元素都小于之前的最大值，我们就在它们之间建立一条有向边，边的强度也是由左右两侧元素之间的温度差决定的（和单向构造的实现方式相同）。
3.3 测试
我们使用下面的示例测试双向构造：
temp_arr = [20, 24, 22, 25, 27, 23, 21, 19, 18]
adj_arr = construct_adj_arr(temp_arr)
for i, j_w in enumerate(adj_arr):
print(f"{temp_arr[i]:>5}:", end="")
for j, w in j_w:
print(f"({temp_arr[j]}:{w})", end="")
print()
输出结果为：
20:(24:3)
24:
22:(25:3)(27:4)
25:(23:2)(27:2)
27:
23:(24:1)(27:3)
21:(25:3)(27:4)
19:(25:3)(27:4)
18:(25:3)(27:4)
同样输出每个元素和其它元素之间的关系，左侧数字是元素的值，右侧是它和其它元素的相邻关系，每个相邻关系是一个元组 (j, w)，表示元素j与它之间有一条连边，权重为w。
相较于单向构造，我们可以看到，双向构造的结果是一致的，但是它更加优化，因为左侧和右侧整个的区间都已经被考虑过了，它能够更好的处理数组中的特殊情况。
4. 总结
Python中，有多种方式可以根据相邻关系还原数组，其中单向和双向的构造方式最为常用。
在单向构造中，我们使用简单的循环遍历数组，根据规则依次构造每个元素之间的连接关系，只考虑之前的元素。
而在双向构造中，我们分别从数组的两端出发，根据规则依次构造元素之间的连接关系，考虑左右两端元素之间的关系。
在具体的使用中，我们需要根据实际情况来选择使用哪种方式，不同的方式有着不同的优缺点。在遍历数组时，我们应该注意特殊的情况，例如左右两端都很相似或相同，需要特别处理。