元素和最小的山形三元组II-LeetCode

2909. 元素和最小的山形三元组II

🎯 问题描述

描述：
给你一个下标从 0 开始的整数数组 nums。
请你找出并返回满足以下条件的最小三元组和：

1. 存在下标 $i, j, k$ 满足 $0 \le i < j < k < n$。
2. 满足“山形”条件：$nums[i] < nums[j]$ 且 $nums[k] < nums[j]$。
3. 目标是使 $nums[i] + nums[j] + nums[k]$ 的值最小。

如果不存在这样的三元组，返回 -1。

说明：

• 这是一个前后缀分解（或预处理）的问题。

• 核心策略：我们可以枚举中间的元素 $nums[j]$。

• 为了使总和最小，对于固定的 $j$，我们需要在 $j$ 的左侧找到最小的 $nums[i]$（满足 $nums[i] < nums[j]$），在 $j$ 的右侧找到最小的 $nums[k]$（满足 $nums[k] < nums[j]$）。

• 通过预处理后缀最小值，我们可以将查找时间降低到 $O(1)$。

• 示例：

• 示例 1：

输入：nums = [5, 6, 1, 2, 3]
输出：8
解释：
- 选择 i=0, j=1, k=2。
- nums[0]=5, nums[1]=6, nums[2]=1。
- 满足 5 < 6 且 1 < 6。
- 和为 5 + 6 + 1 = 12。
- 更好的选择：i=2, j=3, k=? 不行，2 < 3 但后面没有比3小的。
- 实际上：i=2(1), j=3(2), 后面没更小的。
- 让我们看代码逻辑：
- j=1 (6): 左边最小5, 右边最小1. 5<6>1. Sum = 5+6+1=12.
- j=3 (2): 左边最小5(实际上是1), 右边最小3. 1<2<3 (不满足).
- 正确答案应该是 12? 或者是其他组合。
- 无论如何，代码逻辑是寻找 pre < nums[j] > suf[j+1]。

💻 解题思路

思路1：后缀最小值 + 前缀动态维护

核心逻辑

1. 预处理后缀最小值：
   • 构建一个数组 suf，其中 suf[i] 表示 nums[i...n-1] 范围内的最小值。
   • 这样，对于任意 $j$，我们可以在 $O(1)$ 时间内知道其右侧是否存在比它小的数（即 suf[j+1]）。
2. 动态维护前缀最小值：
   • 在遍历中间元素 $j$ 时，用一个变量 pre 记录 nums[0...j-1] 范围内的最小值。
3. 枚举中间点 $j$：
   • 遍历 $j$ 从 $1$ 到 $n-2$。
   • 检查是否满足“山形”条件：pre < nums[j] 且 suf[j+1] < nums[j]。
   • 如果满足，更新答案 ans = min(ans, pre + nums[j] + suf[j+1])。
   • 更新 pre，供下一个 $j$ 使用。

代码实现

class Solution:
    def minimumSum(self, nums: List[int]) -> int:
        n = len(nums)
        
        # 1. 预处理后缀最小值
        # suf[i] 表示 nums[i...n-1] 中的最小值
        suf = [-1] * n
        suf[-1] = nums[-1]
        for i in range(n - 2, -1, -1):
            suf[i] = min(suf[i + 1], nums[i])
        
        # 2. 遍历中间点 j，同时维护前缀最小值 pre
        pre = nums[0]  # pre 表示 nums[0...j-1] 中的最小值
        ans = 3 * 10**8  # 初始化为一个大数
        
        for j in range(1, n - 1):
            # 3. 检查是否构成山形三元组
            # 左边最小值 < 中间值 > 右边最小值
            if pre < nums[j] > suf[j + 1]:
                ans = min(ans, pre + nums[j] + suf[j + 1])
            
            # 4. 更新前缀最小值
            pre = min(pre, nums[j])
            
        return ans if ans != 3 * 10**8 else -1

📊 性能分析

• 时间复杂度：$O(N)$
  • 其中 $N$ 是 nums 的长度。
  • 构建后缀数组需要一次遍历 $O(N)$。
  • 枚举中间点 $j$ 需要一次遍历 $O(N)$。
  • 总时间复杂度为 $O(N)$。
• 空间复杂度：$O(N)$
  • 需要一个长度为 $N$ 的数组 suf 来存储后缀最小值。

思考

1. 为什么使用前缀最小值 pre 和后缀最小值 suf？

   • 题目要求 $nums[i] < nums[j]$ 和 $nums[k] < nums[j]$。
   • 为了使总和 $nums[i] + nums[j] + nums[k]$ 最小，在 $nums[j]$ 固定的情况下，我们需要 $nums[i]$ 和 $nums[k]$ 尽可能小。
   • 因此，对于每个 $j$，我们只需要考虑左侧的最小值和右侧的最小值。

2. 后缀数组的构建：

   • suf[i] = min(suf[i+1], nums[i])。
   • 这保证了 suf[i] 包含了从 i 到末尾的所有元素的最小值。
   • 当我们检查 $j$ 时，右侧的范围是 $j+1$ 到 $n-1$，所以使用 suf[j+1]。

3. 前缀变量的更新：

   • pre 初始化为 nums[0]。
   • 在每次循环结束时，pre = min(pre, nums[j])。
   • 这保证了当循环到 $j+1$ 时，pre 存储的是 nums[0...j] 的最小值，正好是下一轮迭代的左侧范围。

4. 边界条件：

   • $j$ 的范围是 $1$ 到 $n-2$。
   • 因为 $i$ 至少为 0，$k$ 至多为 $n-1$，所以 $j$ 不能是第一个或最后一个元素。

5. 哨兵值：

   • ans 初始化为 3 * 10**8，这是根据题目约束（nums[i] <= 10^8）设定的一个足够大的数。
   • 最后通过比较 ans 是否改变来判断是否找到了解。