JZX轻语：简
LeetCode 845 - 数组中的最长山脉
发表于2024年05月14日
这种涉及两侧计算的数组问题一般都可以考虑使用双侧前/后缀和的思想来维护阶段信息，对于此问题，使用两个数组l2r_inc_cnt和r2l_inc_cnt分别维护某个元素左侧/右侧连续递增的最大长度(不包括该元素)。然后再重新遍历一次数组，对于下标i，取l2r_inc_cnt[i] + r2l_inc_cnt[i] + 1的最大者即可。
进阶要求一次遍历+O(1)空间复杂度，可以考虑使用双指针，两个指针left和right分别指向山峰左右两侧的山脚，然后取right - left + 1的最大者即可。需要留意的是连续重复值的处理，可以使用peak记录山顶的位置，如果peak和right的位置一致(说明arr[peak] == arr[right])，不构成题意的山峰，跳过此次的处理，并将right快速移向不重复的地方。
class Solution:
def longestMountain(self, arr: List[int]) -> int:
l2r_inc_cnt = [0] * len(arr)
r2l_inc_cnt = [0] * len(arr)
for i in range(1, len(arr)):
if arr[i] > arr[i - 1]:
l2r_inc_cnt[i] = l2r_inc_cnt[i - 1] + 1
else:
l2r_inc_cnt[i] = 0
for i in range(len(arr) - 2, -1, -1):
if arr[i] > arr[i + 1]:
r2l_inc_cnt[i] = r2l_inc_cnt[i + 1] + 1
else:
r2l_inc_cnt[i] = 0
ans = 0
for i in range(1, len(arr) - 1):
if l2r_inc_cnt[i] != 0 and r2l_inc_cnt[i] != 0:
ans = max(ans, l2r_inc_cnt[i] + r2l_inc_cnt[i] + 1)
return ans使用双指针的做法：
class Solution:
def longestMountain(self, arr: List[int]) -> int:
n = len(arr)
ans = 0
# left, right分别指向山峰的左右两山脚位置
# 初始化时, left, right先定位到第一个山脚
left = 0
while left < n - 2 and arr[left] >= arr[left + 1]:
left += 1
right = left
while left < n - 2: # 山峰至少有三个数组成, 因此左山脚至多只能到n - 3
# right移向下一个山脚
# 先移向山顶(严格递增)
while right < n - 1 and arr[right] < arr[right + 1]:
right += 1
peak = right
# 再往下移向山底(严格递减)
while right < n - 1 and arr[right] > arr[right + 1]:
right += 1
# 重复值的处理(即会发生 peak == left (== right) or peak == right)
if peak != right and peak != left:
ans = max(ans, right - left + 1)
else:
# 如果有重复值, right快速跳过所有的连续重复值
while right < n - 1 and arr[right] == arr[right + 1]:
right += 1
left = right
return ans