调试中...
困难
相关标签
相关企业
提示
数组 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
通过次数
3.5K
提交次数
12.1K
通过率
28.6%
相关企业
提示 1
Let
p[i] be whether nums[i] is a peak in the original array. Namely p[i] = nums[i] > nums[i - 1] && nums[i] > nums[i + 1].提示 2
Updating
nums[i], only affects p[i], p[i - 1] and p[i + 1]. We can recalculate the 3 values in constant time.提示 3
The answer for
[li, ri] is p[li + 1] + p[li + 2] + … + p[ri - 1] (note that li and ri are not included).提示 4
Use some data structures (i.e. segment tree or binary indexed tree) to maintain the subarray sum efficiently.
评论 (0)
贡献者
© 2025 领扣网络（上海）有限公司
0 人在线