Medium

题目描述

给定一个整数数组 nums，数组中相邻的整数将进行浮点除法运算。

例如，对于 nums = [2,3,4]，我们将计算表达式 "2/3/4"。

但是，你可以在任何位置添加任意数量的括号来改变运算的优先级。你需要添加这些括号，使得表达式计算后的值最大。

以字符串格式返回具有最大值的相应表达式。

注意： 你的表达式不应包含冗余的括号。

示例 1：

输入：nums = [1000,100,10,2]
输出："1000/(100/10/2)"
解释：1000/(100/10/2) = 1000/((100/10)/2) = 200
然而，"1000/((100/10)/2)" 中的粗体括号是冗余的，因为它们不会影响运算优先级。
所以你应该返回 "1000/(100/10/2)"。
其他情况：
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2

示例 2：

输入：nums = [2,3,4]
输出："2/(3/4)"
解释：(2/(3/4)) = 8/3 = 2.667
可以证明，在尝试所有可能性后，我们无法得到计算值大于 2.667 的表达式。

约束条件：

  • 1 <= nums.length <= 10
  • 2 <= nums[i] <= 1000
  • 对于给定的输入，只有一个最优除法。

解题思路

这道题要求我们通过添加括号来最大化除法表达式的结果。

核心思路分析：

  1. 观察数学规律：要最大化 a/b/c/d/... 的值，我们需要让分子尽可能大，分母尽可能小。

  2. 关键洞察：对于形如 a/(b/c/d/...) 的表达式，等价于 a*(c*d*...)/(b)。这样我们就把除法转换为乘法，从而最大化结果。

  3. 最优策略：

    • 当数组长度为1时，直接返回该数字
    • 当数组长度为2时，返回 "a/b"
    • 当数组长度≥3时，最优解是 "a/(b/c/d/...)"，即第一个数除以后面所有数的连续除法

  4. 为什么这是最优的：

    • 原式：a/b/c/d = ((a/b)/c)/d = a/(b*c*d)
    • 加括号后：a/(b/c/d) = a/(b/(c*d)) = a*c*d/b
    • 显然 a*c*d/b > a/(b*c*d)，因为分母变小了

这个策略保证了除了第一个数作为分子外，其余所有数都会通过巧妙的括号安排成为分子的一部分。

代码实现

class Solution {
public:
    string optimalDivision(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return to_string(nums[0]);
        if (n == 2) return to_string(nums[0]) + "/" + to_string(nums[1]);
        
        string result = to_string(nums[0]) + "/(";
        for (int i = 1; i < n; i++) {
            if (i > 1) result += "/";
            result += to_string(nums[i]);
        }
        result += ")";
        return result;
    }
};

class Solution:
    def optimalDivision(self, nums: List[int]) -> str:
        n = len(nums)
        if n == 1:
            return str(nums[0])
        if n == 2:
            return str(nums[0]) + "/" + str(nums[1])
        
        result = str(nums[0]) + "/("
        for i in range(1, n):
            if i > 1:
                result += "/"
            result += str(nums[i])
        result += ")"
        return result

public class Solution {
    public string OptimalDivision(int[] nums) {
        int n = nums.Length;
        if (n == 1) return nums[0].ToString();
        if (n == 2) return nums[0] + "/" + nums[1];
        
        string result = nums[0] + "/(";
        for (int i = 1; i < n; i++) {
            if (i > 1) result += "/";
            result += nums[i];
        }
        result += ")";
        return result;
    }
}

/**
 * @param {number[]} nums
 * @return {string}
 */
var optimalDivision = function(nums) {
    if (nums.length === 1) {
        return nums[0].toString();
    }
    if (nums.length === 2) {
        return nums[0] + "/" + nums[1];
    }
    
    let result = nums[0] + "/(" + nums[1];
    for (let i = 2; i < nums.length; i++) {
        result += "/" + nums[i];
    }
    result += ")";
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(n)

说明：

  • 时间复杂度：需要遍历数组一次来构建结果字符串
  • 空间复杂度：需要额外的字符串空间来存储结果