题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个整型数组，现在定义一个山形三元组，由数组中三个不同的数字组成，要求这三个数的位置上中间的数大于两边的数。如果存在这么山形三元组，那么就求元素和最小的那个三元组的元素和。

思路分享

  • 这是枚举中间类型的第一题，所以将会详细介绍为什么这么做，以及怎么做。

    https://leetcode.cn/problems/minimum-sum-of-mountain-triplets-ii/solutions/2493548/mei-ju-numsj-qian-hou-zhui-fen-jie-pytho-tskf/

  • 首先，为什么要枚举中间。可以看到，题目有三个下标等我们求，如果直接暴力，那么时间复杂度就是 O(n^3)，非常大。枚举中间可以简化时间复杂度到 O(n)（反正会少）。

  • 可不可以枚举左边或者右边呢？应该可以，但大部分情况下没有中间简单。比如要求 i < j < k，如果枚举 j，就不需要考虑 i 和 k 的关系，因为如果 i < j 和 j < k 都满足了，i < k 也会顺便满足。

  • 那么怎么实现同时考虑三个的枚举呢？此前我们是采用哈希表解决一个变量，同时遍历另一个变量，那么我们只要再做预处理，使得第三个变量也能O(1)解决即可。

  • 以本题为例，需要枚举中间的同时，保证两旁的数字比中间小即可，那么如果能通过预处理，知道每个下标位置往右最小的值，那么不就搞定第三个了嘛。

  • 那么第一个变量也可以用这个方法吗？可以，但没必要，因为遍历的过程中，可以维护一个变量，记录当前遍历位置以左的最小值。

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def minimumSum(self, nums: List[int]) -> int:
        n = len(nums)
        suf = [0] * n
        suf[-1] = nums[-1]
        for i in range(n-2, 1, -1):
            print(f"{suf[i+1]} and {nums[i]}")
            suf[i] = min(suf[i+1], nums[i])
        
        ans = inf
        pre = nums[0]
        for i in range(1, n-1):
            if pre < nums[i] > suf[i+1]:
                ans = min(ans, pre + nums[i] + suf[i+1])
            pre = min(pre, nums[i])

        return ans if ans != inf else -1