题目描述与示例

题目描述

给航天器一侧加装长方形或正方形的太阳能板(图中的红色斜线区域),需要先安装两个支柱(图中的黑色竖条),再在支柱的中间部分固定太阳能板。但航天器不同位置的支柱长度不同,太阳能板的安装面积受限于最短一侧的那根支柱长度。如图:

img

现提供一组整形数组的支柱高度数据,假设每根支柱间距离相等为1个单位长度,计算如何选择两根支柱可以使太阳能板的面积最大。

输入描述

10,9,8,7,6,5,4,3,2,1

注:支柱至少有2根,最多10000根,能支持的高度范围1~10^9的整数。柱子的高度是无序的,例子中递减只是巧合。

输出描述

可以支持的最大太阳能板面积:

如:2510米高支柱和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++)⽬录汇总(每⽇更新)

声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。