LeetCode 题解工作台
三段式数组 II
给你一个长度为 n 的整数数组 nums 。 三段式子数组 是一个连续子数组 nums[l...r] （满足 0 ），并且存在下标 l ，使得： nums[l...p] 严格 递增， nums[p...q] 严格 递减， nums[q...r] 严格 递增。 请你从数组 nums 的所有三段式子数组…
0
题型
6
代码语言
0
相关题
当前训练重点
困难 · trionic·数组·ii·core·interview·pattern
答案摘要
我们可以遍历数组，寻找所有可能的极大三段式子数组，从而计算其和并更新最大值。 我们定义一个指针 ，初始时 $i = 0$，表示当前指向数组的第一个元素。我们将 向右移动，直到找到第一个不满足严格递增的元素，即 $nums[i-1] \geq nums[i]$。如果此时 $i = l + 1$，说明这一段只有一个元素，无法形成递增序列，因此继续下一个循环。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 trionic·数组·ii·core·interview·pattern 题型思路
题目描述
给你一个长度为 n 的整数数组 nums。
三段式子数组 是一个连续子数组 nums[l...r]（满足 0 <= l < r < n），并且存在下标 l < p < q < r，使得：
nums[l...p]严格 递增，nums[p...q]严格 递减，nums[q...r]严格 递增。
请你从数组 nums 的所有三段式子数组中找出和最大的那个，并返回其 最大 和。
示例 1：
输入：nums = [0,-2,-1,-3,0,2,-1]
输出：-4
解释：
选择 l = 1, p = 2, q = 3, r = 5：
nums[l...p] = nums[1...2] = [-2, -1]严格递增 (-2 < -1)。nums[p...q] = nums[2...3] = [-1, -3]严格递减 (-1 > -3)。nums[q...r] = nums[3...5] = [-3, 0, 2]严格递增 (-3 < 0 < 2)。- 和 =
(-2) + (-1) + (-3) + 0 + 2 = -4。
示例 2:
输入: nums = [1,4,2,7]
输出: 14
解释:
选择 l = 0, p = 1, q = 2, r = 3：
nums[l...p] = nums[0...1] = [1, 4]严格递增 (1 < 4)。nums[p...q] = nums[1...2] = [4, 2]严格递减 (4 > 2)。nums[q...r] = nums[2...3] = [2, 7]严格递增 (2 < 7)。- 和 =
1 + 4 + 2 + 7 = 14。
提示:
4 <= n = nums.length <= 105-109 <= nums[i] <= 109- 保证至少存在一个三段式子数组。
解题思路
方法一：分组循环
我们可以遍历数组，寻找所有可能的极大三段式子数组，从而计算其和并更新最大值。
我们定义一个指针 ，初始时 ，表示当前指向数组的第一个元素。我们将 向右移动，直到找到第一个不满足严格递增的元素，即 。如果此时 ，说明这一段只有一个元素，无法形成递增序列，因此继续下一个循环。
接下来，我们定义指针 ，表示当前递增段的结束位置。然后找出第二段严格递减的部分，如果这一段只有一个元素或者到达数组末尾，或者出现相等的元素，则继续下一个循环。
然后我们定义指针 ，表示当前递减段的结束位置。接着找出第三段严格递增的部分，这时，我们就找到了一个极大的三段式子数组。那么这个三段式子数组的最大和，由以下几个部分组成：
- 下标范围 的元素之和
- 从 向左扩展的最大递增子数组之和，如果不存在则为 0
- 从 向右扩展的最大递增子数组之和，如果不存在则为 0。
我们计算出这个三段式子数组的和后，更新答案。然后将指针 移动到 位置，这是因为第三段的递增部分可以作为下一次循环的第一段递增部分。
遍历结束后，返回答案即可。
时间复杂度 ，其中 是数组的长度。空间复杂度 ，只使用了常数级别的额外空间。
class Solution:
def maxSumTrionic(self, nums: List[int]) -> int:
n = len(nums)
i = 0
ans = -inf
while i < n:
l = i
i += 1
while i < n and nums[i - 1] < nums[i]:
i += 1
if i == l + 1:
continue
p = i - 1
s = nums[p - 1] + nums[p]
while i < n and nums[i - 1] > nums[i]:
s += nums[i]
i += 1
if i == p + 1 or i == n or nums[i - 1] == nums[i]:
continue
q = i - 1
s += nums[i]
i += 1
mx = t = 0
while i < n and nums[i - 1] < nums[i]:
t += nums[i]
i += 1
mx = max(mx, t)
s += mx
mx = t = 0
for j in range(p - 2, l - 1, -1):
t += nums[j]
mx = max(mx, t)
s += mx
ans = max(ans, s)
i = q
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for the candidate's understanding of dynamic programming in solving subarray problems.
- question_mark
Evaluate how well the candidate optimizes their approach using techniques like prefix sum or sliding windows.
- question_mark
Check if the candidate can handle large input sizes efficiently while maintaining clarity in their solution.
常见陷阱
外企场景- error
Not recognizing the need for dynamic programming, leading to inefficient brute force solutions.
- error
Failing to optimize the solution, resulting in time complexity that does not scale well for larger input sizes.
- error
Incorrectly identifying or implementing the trionic subarray definition, leading to incorrect results.
进阶变体
外企场景- arrow_right_alt
Trionic subarrays with additional constraints, such as limiting the sum within a range.
- arrow_right_alt
Non-contiguous trionic subarrays where the separation condition between indices is relaxed.
- arrow_right_alt
Trionic subarray problems where we need to calculate both sum and product within the subarray.