Geeksforgeeks https://www.geeksforgeeks.org/find-indices-of-all-local-maxima-and-local-minima-in-an-array/的实现是错误的。如果你有连续的重复，事情就会分崩离析!
Example 1: values = [ 1, 2, 3, 7, 11, 15, 13, 12, 11, 6, 5, 7, 11, 8]
The default implementation correctly identify "15" as a peak.
Example 2: values = [ 1, 2, 3, 7, 11, 15, 15, 13, 12, 11, 6, 5, 7, 11, 8]
The default implementation will mark "11" as local maxima because there are two consecutive 15's.
下面是来自geekforgeeks的代码，突出了一个问题——当与左/右进行大/小比较时，如果你的邻居的值==，那么再向左或向右看:
def findLocalMaximaMinima(n, arr):
# Empty lists to store points of
# local maxima and minima
mx = []
mn = []
# Checking whether the first point is
# local maxima or minima or neither
if(arr[0] > arr[1]):
mx.append(0)
elif(arr[0] < arr[1]):
mn.append(0)
# Iterating over all points to check
# local maxima and local minima
for i in range(1, n-1):
# Condition for local minima
if(arr[i-1] > arr[i] < arr[i + 1]): <-- Problem is here
mn.append(i)
# Condition for local maxima
elif(arr[i-1] < arr[i] > arr[i + 1]): <-- Problem is here
mx.append(i)
# Checking whether the last point is
# local maxima or minima or neither
if(arr[-1] > arr[-2]):
mx.append(n-1)
elif(arr[-1] < arr[-2]):
mn.append(n-1)
# Print all the local maxima and
# local minima indexes stored
if(len(mx) > 0):
print("Points of Local maxima"
" are : ", end ='')
print(*mx)
else:
print("There are no points of"
" Local maxima.")
if(len(mn) > 0):
print("Points of Local minima"
" are : ", end ='')
print(*mn)
else:
print("There are no points"
" of Local minima.")
修复方法如下(由于某些原因我不能在那里上传代码，所以在这里上传):
from datetime import datetime
from typing import List
def is_greater(index1, index2, values, increment_when_eq : bool):
if values[index1]>values[index2]:
return True
elif values[index1]<values[index2]:
return False
else:
# Case when: values[index1] == values[index2]
index2_shifted = index2+1 if increment_when_eq else index2-1
if index2_shifted < len(values):
return is_greater(index1=index1, index2 = index2_shifted, values = values, increment_when_eq = increment_when_eq)
else:
return False
def find_local_max_min(values : List):
mx = []
mn = []
n = len(values)
if n==0:
return None
if(values[0] > values[1]):
mx.append(0)
elif(values[0] < values[1]):
mn.append(0)
for i in range(1, n-1):
if (not is_greater(i, i-1, values, False) and not is_greater(i, i+1, values, True)):
mn.append(i)
elif(is_greater(i, i-1, values, False) and is_greater(i, i+1, values, True)):
mx.append(i)
if(values[-1] > values[-2]):
mx.append(n-1)
elif(values[-1] < values[-2]):
mn.append(n-1)
return {
'local_max' : mx,
'local_min' : mn
}
if __name__ == '__main__':
values = [ 1, 2, 3, 7, 11, 15, 15, 13, 12, 11, 6, 5, 7, 11 , 8, 19, 19, 18, 18, 18, 15, 7, 3]
start = datetime.now()
local_min_max = find_local_max_min(values)
local_max = local_min_max['local_max']
local_min = local_min_max['local_min']
我同意Pranav的观点，只要在进行比较时解决平等问题就能纠正问题。修复将更加简洁。由于Pranav
def findLocalMaximaMinima(n, arr):
mx = []
mn = []
if(arr[0] > arr[1]):
mx.append(0)
elif(arr[0] < arr[1]):
mn.append(0)
for i in range(1, n-1):
if(arr[i-1] >= arr[i] < arr[i + 1]):
mn.append(i)
elif(arr[i-1] < arr[i] >= arr[i + 1]):
mx.append(i)
if(arr[-1] > arr[-2]):
mx.append(n-1)
elif(arr[-1] < arr[-2]):
mn.append(n-1)
return mx, mn
arrs = [[ 1, 2, 3, 7, 11, 15, 15, 13, 12, 11, 6, 5, 7, 11, 8],
[4, 5, 6, 6, 6, 4, 3, 2, 1, 3, 5, 7, 9]]
for arr in arrs:
mx, mn = findLocalMaximaMinima(len(arr), arr)
print(*[f"{a}, {'max'*(i in mx)}, {'min' * (i in mn)}" for i, a in enumerate(arr)], sep='n', end='nn')
https://tio.run/# # bVLhboIwEP7PU1z8A3V1sTqdM7onmE/A@qMZZWsCJ6mYsBifnbVXVFggQK5fv@@79u6q3/rniMu2zXQOucHs4/ilioNqTKkOBt0/QQ7KWraNwD1lA3tIZYgxxLQweeJY6VzCu6enQnaKoHpWVaUxS@aMQF08@LsRPvb4hOZHCwYMglX4rRPBAWeip@jszEy4A@zJ0dysDTzBwH6YwrD7xv1Y5LO72dwMR32ank@/EnQS0s0W47XwNxhW45H1nwYHGsKtrs8WnR1321HkRCffjhRcbRYclhxeOQi3EKvuc5BYBGzNYXUnbCSP0g0t1/S@kNxTKQjMNykj3wWXyPfB59tG3UzwMAvj81No9JdjYYxIUVmDdTJN88lFXTlc4lI18TShBpcNC5DBGKbQgciukzAEzsYjGs@ltqrW5C05nHS1jz8x5m4r85GLWdv@AQ