LeetCode Weekly Contest 368 第1, 2 題 Minimum Sum of Mountain Triplets

原題目：2909. Minimum Sum of Mountain Triplets II

給一個正整數陣列求最小 (i, j, k) 的和，(i, j, k) 須滿足以下兩個條件：

1. i < j < k
2. nums[i] < nums[j] and nums[k] < nums[j]

第一題的編號是 2908，直接依照題目給的條件寫三層迴圈就能通過了。時間複雜度 O(n³)。

class Solution:
    def minimumSum(self, nums: List[int]) -> int:
        min_total = float('inf')
        n = len(nums)
        for i in range(0, n-2):
            for j in range(1, n-1):
                for k in range(2, n):
                    if (i < j < k) and (nums[i] < nums[j] and nums[k] < nums[j]):
                        min_total = min(nums[i] + nums[j] + nums[k], min_total)
                    
        return -1 if min_total == float('inf') else min_total

第二題 nums.length 10⁵ 這樣寫會TLE，要用 Prefix Min 的做法，時間複雜度 O(n)。

因為 i < j < k，就是整個數列依序取三個數出來，假設有一個解是 (l, pivot, r)，分別在 2, 5, 8 的位置：

如果 (l, pivot, r) 要是最小，l 一定要是 pivot 之前所有數中最小的，r 也是一樣，會是 pivot 之後的所有數中最小的那個。然後再從 i = 0 開始找有最小值的 pivot 就可以了。

class Solution:
    def minimumSum(self, nums: List[int]) -> int:
        n = len(nums)
        min_l = [nums[0]]
        for i in range(1, n):
            min_l.append(min(min_l[i-1], nums[i]))

        min_r = [0 for i in range(n)]
        min_r[-1] = nums[-1]
        for i in range(n-2, -1, -1):
            min_r[i] = min(min_r[i+1], nums[i])

        total = float('inf')
        for i in range(1, n-1):
            if min_l[i] < nums[i] and nums[i] > min_r[i]:
                total = min(total, min_l[i] + nums[i] + min_r[i])

        return -1 if total == float('inf') else total

min_l 是 pivot 左邊的最小值陣列，min_r 是 pivot 右邊的最小值陣列，min_l[i] 代表到第 i 個為止最左邊的值，min_r[i] 代表從右邊數回來第 i 個為止最小的值。找法是 nums[0] 和 nums[len(nums)-1] 分別是 min_l 和 min_r 的最小值，接著每個 nums[i] 都跟 min_l[i-1] 和 min_r[i+1] 比哪個比較小，比較小的那個就是 min_l 或 min_r [i] 的值。

做完這兩個陣列之後再遍歷一次 nums 找符合題目要的 mountain triplets 最小值就行了。