LeetCode 题解工作台
数组中的峰值
数组 arr 中 大于 前面和后面相邻元素的元素被称为 峰值 元素。 给你一个整数数组 nums 和一个二维整数数组 queries 。 你需要处理以下两种类型的操作： queries[i] = [1, l i , r i ] ，求出子数组 nums[l i ..r i ] 中 峰值 元素的数目。 …
3
题型
7
代码语言
3
相关题
当前训练重点
困难 · 数组·结合·二分·indexed·树
答案摘要
根据题目描述，对于 $0 < i < n - 1$，如果满足 $nums[i - 1] < nums[i]$ 且 $nums[i] > nums[i + 1]$，我们可以将 视为 ，否则视为 。这样，对于操作 ，即查询子数组 中的峰值元素个数，相当于查询区间 $[l + 1, r - 1]$ 中 的个数。我们可以使用树状数组来维护区间 $[1, n - 1]$ 中 的个数。 而对于操作 ，…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·结合·二分·indexed·树 题型思路
题目描述
数组 arr 中 大于 前面和后面相邻元素的元素被称为 峰值 元素。
给你一个整数数组 nums 和一个二维整数数组 queries 。
你需要处理以下两种类型的操作：
queries[i] = [1, li, ri]，求出子数组nums[li..ri]中 峰值 元素的数目。queries[i] = [2, indexi, vali]，将nums[indexi]变为vali。
请你返回一个数组 answer ，它依次包含每一个第一种操作的答案。
注意：
- 子数组中 第一个 和 最后一个 元素都 不是 峰值元素。
示例 1：
输入：nums = [3,1,4,2,5], queries = [[2,3,4],[1,0,4]]
输出：[0]
解释：
第一个操作：我们将 nums[3] 变为 4 ，nums 变为 [3,1,4,4,5] 。
第二个操作：[3,1,4,4,5] 中峰值元素的数目为 0 。
示例 2：
输入：nums = [4,1,4,2,1,5], queries = [[2,2,4],[1,0,2],[1,0,4]]
输出：[0,1]
解释：
第一个操作：nums[2] 变为 4 ，它已经是 4 了，所以保持不变。
第二个操作：[4,1,4] 中峰值元素的数目为 0 。
第三个操作：第二个 4 是 [4,1,4,2,1] 中的峰值元素。
提示：
3 <= nums.length <= 1051 <= nums[i] <= 1051 <= queries.length <= 105queries[i][0] == 1或者queries[i][0] == 2- 对于所有的
i，都有：queries[i][0] == 1：0 <= queries[i][1] <= queries[i][2] <= nums.length - 1queries[i][0] == 2：0 <= queries[i][1] <= nums.length - 1,1 <= queries[i][2] <= 105
解题思路
方法一：树状数组
根据题目描述，对于 ，如果满足 且 ，我们可以将 视为 ，否则视为 。这样，对于操作 ，即查询子数组 中的峰值元素个数，相当于查询区间 中 的个数。我们可以使用树状数组来维护区间 中 的个数。
而对于操作 ，即把 更新为 ，只会影响到 , , 这三个位置的值，因此我们只需要更新这三个位置即可。具体地，我们可以先把这三个位置的峰值元素去掉，然后更新 的值，最后再把这三个位置的峰值元素加回来。
时间复杂度 ，空间复杂度 。其中 和 分别是数组 nums 的长度和查询数组 queries 的长度。
class BinaryIndexedTree:
__slots__ = "n", "c"
def __init__(self, n: int):
self.n = n
self.c = [0] * (n + 1)
def update(self, x: int, delta: int) -> None:
while x <= self.n:
self.c[x] += delta
x += x & -x
def query(self, x: int) -> int:
s = 0
while x:
s += self.c[x]
x -= x & -x
return s
class Solution:
def countOfPeaks(self, nums: List[int], queries: List[List[int]]) -> List[int]:
def update(i: int, val: int):
if i <= 0 or i >= n - 1:
return
if nums[i - 1] < nums[i] and nums[i] > nums[i + 1]:
tree.update(i, val)
n = len(nums)
tree = BinaryIndexedTree(n - 1)
for i in range(1, n - 1):
update(i, 1)
ans = []
for q in queries:
if q[0] == 1:
l, r = q[1] + 1, q[2] - 1
ans.append(0 if l > r else tree.query(r) - tree.query(l - 1))
else:
idx, val = q[1:]
for i in range(idx - 1, idx + 2):
update(i, -1)
nums[idx] = val
for i in range(idx - 1, idx + 2):
update(i, 1)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O((n + q) log n) using a BIT, where n is the array size and q is the number of queries. Space complexity is O(n) for storing peaks and BIT structure. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The problem expects efficient peak counting under frequent updates.
- question_mark
Mentioning a BIT or Segment Tree is a strong signal you understand range update patterns.
- question_mark
Handling boundary indices correctly is often probed for robustness.
常见陷阱
外企场景- error
Not updating neighboring peak indicators after a value change, leading to incorrect counts.
- error
Forgetting to check array bounds when computing peaks, causing runtime errors.
- error
Using naive recalculation of all peaks per query results in TLE for large inputs.
进阶变体
外企场景- arrow_right_alt
Compute valleys instead of peaks using similar BIT or Segment Tree logic.
- arrow_right_alt
Allow range increments for type-1 queries, requiring more advanced lazy propagation.
- arrow_right_alt
Count peaks modulo a number to combine peak counting with numeric constraints.