发表于 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

• LC 题目链接