蓝桥杯python省赛备战day2--数组枚举--845数组中的最长山脉-枚举算法刷题学习笔记3--leetcode
写在前面的话：
大家好，我是一名正在努力学习数据结构和算法的新手。这篇文章是我在学习python的各类数据结构以及基础算法过程中的一些笔记和心得，希望能和同样在学习该方面知识的朋友们分享。由于我的知识有限，文章中可能存在错误或不准确的地方，欢迎大家在评论区提出建议和指正。我非常期待大家的反馈，以便我能不断学习和进步。同时，我也会在文章中注明参考的资料，以示对原作者的尊重。
PS：本帖以记录学习心得和刷题记录解析为主，没有其他大博主那么专业，但是简单易懂^-^
本贴的其他相关学习笔记资料可以通过订阅专栏获取，喜欢的小伙伴可以多多点赞+关注呀！后续会 持续更新相关资源的~
分析题目：题目要求我们找出从左边递增到山顶，经过山顶后递减的符合要求的数组长度。而我们可以通过枚举法遍历每一个可能为山顶的节点（不包括数组中的第一个和最后一个节点），同时对于每一个可能为山顶的节点向左向右延申判断是否满足山顶条件+计数。最后设置一个变量不都安更新整体数组中的山顶长度最大值即可。
我的实操代码，通过73/75测试用例：
class Solution:
def longestMountain(self, arr: List[int]) -> int:
res=0
for i in range(1, len(arr)-1):
if arr[i-1]<arr[i] and arr[i] > arr[i+1]:
count1=0
if i-2 >=0:
for j in range(i-1,-1,-1):
if arr[j-1]>arr[j]:
break
if arr[j-1]<arr[j]:
count1+=1
count2=0
if i+2 < len(arr):
for k in range(i+2,len(arr)):
if arr[k-1]<arr[k]:
break
if arr[k-1]>arr[k]:
count2+=1
# if count1 >count2:
# a=count2
# else:
# a=count1
# if count1>count2:
# a=count1
# else:
# a=count2
if res < count1+count2+3:
res=count1+count2+3
return res
该代码经过多次调试，仍无法解决一下测试用例，希望懂的小伙伴可以在评论区留言指导指导我呀~
该题目的难点就是确定了一个山顶后，向左向右延申查找符合要求的节点时如何控制索引的问题。
写if判断语句时要注意考虑极端情况，如搜索到数组的两端时，要注意不可以list index out of range；
同时也要考虑并非在左边只要满足左小于右就可以了，只要出现的左大于右就要马上break出循环，否则计数是错误的；
在遍历完山顶的两边后，做一个求和更新res值即可
以下为可以通过全部用例的代码：
from typing import List
class Solution:
def longestMountain(self, arr: List[int]) -> int:
res = 0
n = len(arr)
for i in range(1, n - 1):
# Check if arr[i] is a peak (it must be larger than its neighbors)
if arr[i - 1] < arr[i] and arr[i] > arr[i + 1]:
count1 = 0 # Count elements to the left of the peak
# Move leftwards while the sequence is strictly increasing
while i - count1 - 1 >= 0 and arr[i - count1 - 1] < arr[i - count1]:
count1 += 1
count2 = 0 # Count elements to the right of the peak
# Move rightwards while the sequence is strictly decreasing
while i + count2 + 1 < n and arr[i + count2 + 1] < arr[i + count2]:
count2 += 1
# If there is a valid mountain (i.e., count1 > 0 and count2 > 0)
if count1 > 0 and count2 > 0:
res = max(res, count1 + count2 + 1)
return res
很明显，这个代码就是在向左向右延申的索引里面做文章。这里采用的是利用while循环+利用计数器本身作为迭代器的方式来展开循环（即while判据中含有count），非常巧妙。即i-k-1 and i+k+1的形式，保证了索引不越界+满足大小要求的前提下展开循环。
while循环的使用方法就是判据里面有迭代器变量，缩进里面也有迭代器变量。
总结：这个可以完全通过测试用例的代码亮点在于它是优先保证最接近数组边缘的索引不越界（而我的代码中并没有很好地确保这一点），举个例子，在向左延申时，它是优先确保i - count1 - 1 >= 0即左端的左端索引不越界。（向右延申的话优先确保右端的右端索引不越界）
因此，该代码给我的启发就是在循环中检索数组时要优先确保边缘处不越界。不越界是数组枚举的核心考点之一。
最后，感谢每一位阅读这篇文章的朋友，你们的反馈对我来说非常宝贵。如果有任何问题或建议，请随时告诉我。让我们一起学习和进步吧！如果您喜欢我的内容，别忘了点赞和关注哦，我会定期分享更多有价值的信息。