题目描述
一线运维人员在对通话流量进行监控，每一段时间内都是出现流量的高峰，流量有高有低形成一个个波峰波谷，运维人员想找到流量变化最快的波峰，你可以帮助他吗？ 给定一个整数数组nums，代表采样点的流量值，
请找到满足以下条件的三元组(i,j,k):其中i<j<k，nums[j] > nums[i]且nums[j] > nums[k] (即j是峰顶)，并找到所有满足条件的三元组中(k-i)的最小值 输入描述 第一行为n个整数，表示数组中的n个元素，0<= n < =100000 输出描述 返回所有满足条件的三元组中(k-i)的最小值。若不存在，返回-1。
题目整理
我们有一个数组 nums，要找三元组 (i, j, k) 满足：
i < j < knums[j] > nums[i]且nums[j] > nums[k]也就是说
j是一个峰顶，nums[i]和nums[k]分别在j的左右，并且都比nums[j]小。
目标：在所有这样的三元组中，找到 最小的 k - i 值。
如果不存在这样的三元组，返回 -1。
关键点
峰
j必须严格大于左右两边的值。我们只关心
k - i最小，也就是左右两个谷i和k离得最近。注意
i和k不一定紧挨着j，可以隔开一些元素，只要i < j < k并且nums[i] < nums[j]且nums[k] < nums[j]即可。
我们要找的是所有“山峰” j 的左右最近的小于它的 i 和 k 中 k-i 的最小值。
“最近”是指在所有满足条件的 i 和 k 中，k-i 最小，并不是指 i 和 k 离 j 最近，而是它们之间的距离最小。
问题分析
我们需要找到所有山峰 j，然后为每个 j 找到：
左边最近的比
nums[j]小的数nums[i]右边最近的比
nums[j]小的数nums[k]
然后计算 k-i 的最小值。
def find_small(nums, local):
# 根据方向参数local，统一处理左右较小值查找
# 返回每个位置在指定方向的第一个较小值索引
stack = []
result = [-1] * len(nums)
if local == 'left':
for i in range(len(nums)):
while stack and nums[stack[-1]] >= nums[i]:
stack.pop()
if stack:
result[i] = stack[-1]
stack.append(i)
else:
for i in range(len(nums) - 1, -1, -1):
while stack and nums[stack[-1]] >= nums[i]:
stack.pop()
if stack:
result[i] = stack[-1]
stack.append(i)
return result
def find_all_valid_j(nums):
# 获取左右较小值数组
# 遍历所有可能的位置j(1到n-2)
# 检查j是否满足：左右都有较小值
# 返回所有有效山峰位置
valid_j = []
left_smaller = find_small(nums, 'left')
right_smaller = find_small(nums, 'right')
for j in range(1, len(nums) - 1):
if left_smaller[j] != -1 and right_smaller[j] != -1:
valid_j.append(j)
return valid_j, left_smaller, right_smaller
def cal_min_distance(nums):
# 获取所有有效山峰
# 遍历每个有效山峰，计算k-i距离
# 返回最小距离，无解返回-1
valid_j, left_smaller, right_smaller = find_all_valid_j(nums)
min_distance = float('inf') # min_distance = float('inf') 是初始化最小值为正无穷大。float('-inf') 表示负无穷大
if not valid_j:
return -1
for j in valid_j:
i = left_smaller[j]
k = right_smaller[j]
distance = k - i
min_distance = min(min_distance, distance)
return min_distance
def main():
nums = list(map(int,input().split()))
print(cal_min_distance(nums))
if __name__ == '__main__':
main()算法步骤逻辑总结：
预处理左较小值：使用单调栈从左到右扫描，记录每个元素左边第一个小于它的索引
预处理右较小值：使用单调栈从右到左扫描，记录每个元素右边第一个小于它的索引
识别有效山峰：遍历所有位置，筛选出左右都有较小值的峰顶位置j
计算最小距离：对每个有效山峰，计算其左右较小值索引的距离k-i，取所有距离中的最小值
处理边界情况：若无有效山峰则返回-1
通过单调栈分别找到每个元素左右第一个较小值的索引，然后遍历所有满足山峰条件的位置，计算其左右较小值索引的距离并取最小值。
输入数组 → 单调栈找left_smaller → 单调栈找right_smaller → 识别有效山峰 → 计算最小距离 → 输出结果
↓ ↓ ↓ ↓ ↓ ↓
[3,5,4,7,2,1] → [-1,0,0,2,-1,-1] → [4,2,4,4,5,-1] → [1,2,3] → min(2,4,2) → 2