Leetcode # 2874. ⭐️ Maximum Value of an Ordered Triplet II

Problem

https://leetcode.com/contest/weekly-contest-365/problems/maximum-value-of-an-ordered-triplet-ii/

return max((nums[i] – nums[j]) * nums[k] for i, j, k ∈ 1, 2, …, n if i < j < k)

Testcases

相關例題

• Leetcode # 2873. Maximum Value of an Ordered Triplet I

Solution: Two-Pass

找最小的 num[j]

例: [8,6,3,13,2,12,19,5,19,6,10,11,9]

若以最小的 2 (nums[4]) 為 nums[j]
⇒ (nums[3] – nums[4]) * nums[6] = (13 – 2) * 19 = 209
< 266 = (19 – 5) * 19 = (nums[6] – nums[7]) * nums[8]

Time Complexity: O(n)
Space Complexity: O(n)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def maximumTripletValue(self, nums: List[int]) -> int:
    maxes = [[0, 0] for _ in range(len(nums))]
    m = nums[0]
    for i in range(1, len(nums)):
      maxes[i][0] = m
      m = max(m, nums[i])
    m = nums[-1]
    for i in range(len(nums) - 2, -1, -1):
      maxes[i][1] = m
      m = max(m, nums[i])
    return max(0, max((maxes[i][0] - nums[i]) * maxes[i][1] for i in range(1, len(nums) - 1)))

Solution: One-Pass

找 j 以左最大的 nums[i] 及以右最大的 nums[k]
找 k 以左能滿足最大「(nums[i] – nums[j]) * nums[k]」的 i, j

Time Complexity: O(n)
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def maximumTripletValue(self, nums: List[int]) -> int:
    max_i = max_ij = max_ijk = 0
    for k in range(2, len(nums)):
      max_i   = max(max_i,   nums[k - 2])
      max_ij  = max(max_ij,  max_i - nums[k - 1])
      max_ijk = max(max_ijk, max_ij * nums[k])
    return max_ijk

Last Updated on 2023/10/01 by A1go