题目描述与示例
题目描述
给航天器一侧加装长方形或正方形的太阳能板(图中的红色斜线区域),需要先安装两个支柱(图中的黑色竖条),再在支柱的中间部分固定太阳能板。但航天器不同位置的支柱长度不同,太阳能板的安装面积受限于最短一侧的那根支柱长度。如图:
现提供一组整形数组的支柱高度数据,假设每根支柱间距离相等为1
个单位长度,计算如何选择两根支柱可以使太阳能板的面积最大。
输入描述
10,9,8,7,6,5,4,3,2,1
注:支柱至少有2
根,最多10000
根,能支持的高度范围1~10^9
的整数。柱子的高度是无序的,例子中递减只是巧合。
输出描述
可以支持的最大太阳能板面积:
如:25
(10
米高支柱和5
米高支柱之间)
示例一
输入
10,9,8,7,6,5,4,3,2,1
输出
25
说明
示例二
输入
1,7,5,9
输出
14
说明
7*2=14
解题思路
注意,本题和LC11. 盛最多水的容器完全一致。
代码
# 题目:2023B-太阳能航天器
# 分值:100
# 作者:许老师-闭着眼睛学数理化
# 算法:相向双指针
# 代码看不懂的地方,请直接在群上提问
# 输入所有支柱的高度数组
heights = list(map(int, input().split(",")))
# 获得支柱数量n
n = len(heights)
# 初始化相向双指针,分别指向heights数组中第一个元素和最后一个元素
left, right = 0, n-1
# 初始化答案变量为0
ans = 0
while left < right:
# right-left为当前两个指针所围区域的宽度
# min(heights[left], heights[right]为当前两个指针所围区域的高度
# 两者相乘为当前两个指针所围区域的面积,用来更新ans
ans = max(ans, (right-left) * min(heights[left], heights[right]))
# 区域高度由高度较小的支柱决定
# 当left对应的支柱高于right,即使left向右移动,
# 也不可能使得两者间的较小值比heights[right]更高
# 故应该令right向左移动,才有可能使得高度变大,总面积变大
if heights[left] > heights[right]:
right -= 1
# 反之,则令left向右移动
else:
left += 1
print(ans)
时空复杂度
时间复杂度:O(``N``)
。双指针算法,每一个元素仅需经过一次,仅需一次遍历heights
数组。
空间复杂度:O(``1``)
。仅需若干常数变量。
说明
华为OD机试有三道题⽬,第⼀道和第⼆道属于简单或中等题,分值为 100 分,第三道为中等或困难题,分值为 200分,总分为 400 分。
机试分数越⾼评级越⾼,⼯资也就越⾼。
关于华为 OD 机试更加详细的介绍可以查看这篇⽂章:华为OD机考须知
关于机考题目汇总可以看这篇文章:华为OD机试真题 2023 A+B+C+D卷 + 2024新卷(Python&Java&C++)⽬录汇总(每⽇更新)