题面描述

我们需要在航天器的一侧安装太阳能板。太阳能板的安装需要两根支柱，且太阳能板的面积受限于两根支柱中较短的那根。给定一组支柱的高度数据，假设每根支柱之间的距离相等（1个单位长度），要求选择两根支柱，使得太阳能板的面积最大。

思路

使用双指针法，初始化两个指针分别指向数组的两端，计算当前两根支柱的面积（距离 × 较短支柱高度），并更新最大面积；然后移动较短支柱的指针，逐步缩小范围，直到两指针相遇。时间复杂度为 O(n)，空间复杂度为 O(1)，高效解决了问题。

1. 问题分析：

   • 每两根支柱之间的距离为1个单位长度。
   • 太阳能板的面积 = 两根支柱之间的距离 × 两根支柱中较短的那根高度。
   • 我们需要找到两根支柱，使得它们的距离与较短高度的乘积最大。

2. 算法选择：

   • 直接暴力枚举所有可能的支柱组合，计算面积并取最大值。这种方法的时间复杂度为O(n^2)，对于n=10000来说，可能会超时。
   • 使用双指针法，从数组的两端向中间移动，每次移动较短的那根支柱，以期望找到更大的面积。这种方法的时间复杂度为O(n)。

3. 双指针法的具体步骤：

   • 初始化两个指针，一个指向数组的开头（left），一个指向数组的末尾（right）。
   • 计算当前两根支柱的面积，并更新最大面积。
   • 移动较短的那根支柱的指针（left向右移动或right向左移动）。
   • 重复上述步骤，直到left和right相遇。

cpp

#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm>

using namespace std;

int maxArea(vector<int>& height) {
    int left = 0, right = height.size() - 1;
    int max_area = 0;
    
    while (left < right) {
        // 计算当前两根支柱的面积
        int current_area = min(height[left], height[right]) * (right - left);
        // 更新最大面积
        max_area = max(max_area, current_area);
        
        // 移动较短的那根支柱的指针
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    
    return max_area;
}

int main() {
    string input;
    getline(cin, input); // 获取用户输入
    
    // 将输入字符串转换为整数数组
    vector<int> height;
    stringstream ss(input);
    string token;
    while (getline(ss, token, ',')) {
        height.push_back(stoi(token));
    }
    
    // 计算并输出最大面积
    cout << maxArea(height) << endl;
    return 0;
}

python

def maxArea(height):
    left, right = 0, len(height) - 1
    max_area = 0

    while left < right:
        # 计算当前两根支柱的面积
        current_area = min(height[left], height[right]) * (right - left)
        # 更新最大面积
        max_area = max(max_area, current_area)

        # 移动较短的那根支柱的指针
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_area


# 获取用户输入
input_data = input().strip()  # 去掉首尾空白字符
# 将输入字符串转换为整数列表，并过滤掉空字符串
height = [int(x) for x in input_data.split(',') if x.strip()]
# 计算并输出最大面积
print(maxArea(height))

java

import java.util.Scanner;

public class Main {
    public static int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int maxArea = 0;
        
        while (left < right) {
            // 计算当前两根支柱的面积
            int currentArea = Math.min(height[left], height[right]) * (right - left);
            // 更新最大面积
            maxArea = Math.max(maxArea, currentArea);
            
            // 移动较短的那根支柱的指针
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        
        return maxArea;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine(); // 获取用户输入
        
        // 将输入字符串转换为整数数组
        String[] tokens = input.split(",");
        int[] height = new int[tokens.length];
        for (int i = 0; i < tokens.length; i++) {
            height[i] = Integer.parseInt(tokens[i].trim());
        }
        
        // 计算并输出最大面积
        System.out.println(maxArea(height));
    }
}

题目内容

给航天器一侧加装长方形或正方形的太阳能板（图中的红色斜线区域），需要先安装两个支柱（​图中的黑色竖条​），再在支柱的中间部分固定太阳能板。

但航天器不同位置的支柱长度不同，太阳能板的安装面积受限于最短一侧的那根支柱长度。如图：

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

输入描述

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

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

输出描述

可以支持的最大太阳能板面积：（10米高支柱和5米高支柱之间）

25

样例1

输入

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

输出

25

说明

10米高支柱和5米高支柱之间宽度为5，高度取小的支柱高也是5，面积为25。

任取其他两根支柱所能获得的面积都小于25。

所以最大的太阳能板面积为25。