Hard
题目描述
数组中的峰值是指比其前一个和后一个元素都大的元素。
给你一个整数数组 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,1,4,2,1] 中第二个 4 是峰值。
提示：
3 <= nums.length <= 10^51 <= nums[i] <= 10^51 <= queries.length <= 10^5queries[i][0] == 1 or queries[i][0] == 2- 对于
queries[i][0] == 1：0 <= queries[i][1] <= queries[i][2] <= nums.length - 1 - 对于
queries[i][0] == 2：0 <= queries[i][1] <= nums.length - 1, 1 <= queries[i][2] <= 10^5
解题思路
这是一道涉及动态数组修改和区间查询的问题，需要使用高效的数据结构来维护峰值信息。
核心思路：
峰值判断：位置 i 是峰值当且仅当
nums[i] > nums[i-1] && nums[i] > nums[i+1]，且1 <= i <= n-2影响范围分析：当修改位置 i 的值时，只会影响位置 i-1, i, i+1 三个位置的峰值状态
数据结构选择：使用树状数组（Binary Indexed Tree）或线段树来维护峰值的前缀和，支持：
- 单点更新：O(log n)
- 区间求和：O(log n)
算法流程：
- 初始化一个标记数组
isPeak，记录每个位置是否为峰值 - 建立树状数组，维护峰值的前缀和
- 对于每个查询：
- 类型1（区间查询）：查询范围 [l+1, r-1] 的峰值总数
- 类型2（单点修改）：更新nums[index]，重新计算 index-1, index, index+1 的峰值状态，并更新树状数组
优化要点：
- 查询范围需要排除边界元素，因为它们不能成为峰值
- 修改操作需要先撤销旧状态，再添加新状态
代码实现
class Solution {
public:
class BIT {
vector<int> tree;
int n;
public:
BIT(int size) : n(size) {
tree.resize(n + 1, 0);
}
void update(int i, int delta) {
for (i++; i <= n; i += i & -i) {
tree[i] += delta;
}
}
int query(int i) {
int sum = 0;
for (i++; i > 0; i -= i & -i) {
sum += tree[i];
}
return sum;
}
int rangeQuery(int l, int r) {
if (l > r) return 0;
return query(r) - (l > 0 ? query(l - 1) : 0);
}
};
bool isPeak(vector<int>& nums, int i) {
if (i <= 0 || i >= nums.size() - 1) return false;
return nums[i] > nums[i - 1] && nums[i] > nums[i + 1];
}
vector<int> countOfPeaks(vector<int>& nums, vector<vector<int>>& queries) {
int n = nums.size();
BIT bit(n);
vector<bool> peaks(n, false);
for (int i = 1; i < n - 1; i++) {
if (isPeak(nums, i)) {
peaks[i] = true;
bit.update(i, 1);
}
}
vector<int> result;
for (auto& query : queries) {
if (query[0] == 1) {
int l = query[1], r = query[2];
result.push_back(bit.rangeQuery(l + 1, r - 1));
} else {
int idx = query[1], val = query[2];
for (int i = max(1, idx - 1); i <= min(n - 2, idx + 1); i++) {
if (peaks[i]) {
bit.update(i, -1);
peaks[i] = false;
}
}
nums[idx] = val;
for (int i = max(1, idx - 1); i <= min(n - 2, idx + 1); i++) {
if (isPeak(nums, i)) {
peaks[i] = true;
bit.update(i, 1);
}
}
}
}
return result;
}
};
class Solution:
def countOfPeaks(self, nums: List[int], queries: List[List[int]]) -> List[int]:
class BIT:
def __init__(self, n):
self.n = n
self.tree = [0] * (n + 1)
def update(self, i, delta):
i += 1
while i <= self.n:
self.tree[i] += delta
i += i & (-i)
def query(self, i):
i += 1
res = 0
while i > 0:
res += self.tree[i]
i -= i & (-i)
return res
def range_query(self, l, r):
if l > r:
return 0
return self.query(r) - (self.query(l - 1) if l > 0 else 0)
def is_peak(i):
if i <= 0 or i >= len(nums) - 1:
return False
return nums[i] > nums[i - 1] and nums[i] > nums[i + 1]
n = len(nums)
bit = BIT(n)
peaks = [False] * n
for i in range(1, n - 1):
if is_peak(i):
peaks[i] = True
bit.update(i, 1)
result = []
for query in queries:
if query[0] == 1:
l, r = query[1], query[2]
result.append(bit.range_query(l + 1, r - 1))
else:
idx, val = query[1], query[2]
for i in range(max(1, idx - 1), min(n - 1, idx + 2)):
if peaks[i]:
bit.update(i, -1)
peaks[i] = False
nums[idx] = val
for i in range(max(1, idx - 1), min(n - 1, idx + 2)):
if is_peak(i):
peaks[i] = True
bit.update(i, 1)
return result
public class Solution {
public class BIT {
private int[] tree;
private int n;
public BIT(int size) {
n = size;
tree = new int[n + 1];
}
public void Update(int i, int delta) {
for (i++; i <= n; i += i & -i) {
tree[i] += delta;
}
}
public int Query(int i) {
int sum = 0;
for (i++; i > 0; i -= i & -i) {
sum += tree[i];
}
return sum;
}
public int RangeQuery(int l, int r) {
if (l > r) return 0;
return Query(r) - (l > 0 ? Query(l - 1) : 0);
}
}
private bool IsPeak(int[] nums, int i) {
if (i <= 0 || i >= nums.Length - 1) return false;
return nums[i] > nums[i - 1] && nums[i] > nums[i + 1];
}
public IList<int> CountOfPeaks(int[] nums, int[][] queries) {
int n = nums.Length;
BIT bit = new BIT(n);
bool[] peaks = new bool[n];
for (int i = 1; i < n - 1; i++) {
if (IsPeak(nums, i)) {
peaks[i] = true;
bit.Update(i, 1);
}
}
List<int> result = new List<int>();
foreach (var query in queries) {
if (query[0] == 1) {
int l = query[1], r = query[2];
result.Add(bit.RangeQuery(l + 1, r - 1));
} else {
int idx = query[1], val = query[2];
for (int i = Math.Max(1, idx - 1); i <= Math.Min(n - 2, idx + 1); i++) {
if (peaks[i]) {
bit.Update(i, -1);
peaks[i] = false;
}
}
nums[idx] = val;
for (int i = Math.Max(1, idx - 1); i <= Math.Min(n - 2, idx + 1); i++) {
if (IsPeak(nums, i)) {
peaks[i] = true;
bit.Update(i, 1);
}
}
}
}
return result;
}
}
var countOfPeaks = function(nums, queries) {
class BIT {
constructor(n) {
this.n = n;
this.tree = new Array(n + 1).fill(0);
}
update(i, delta) {
for (i++; i <= this.n; i += i & -i) {
this.tree[i] += delta;
}
}
query(i) {
let sum = 0;
for (i++; i > 0; i -= i & -i) {
sum += this.tree[i];
}
return sum;
}
rangeQuery(l, r) {
if (l > r) return 0;
return this.query(r) - (l > 0 ? this.query(l - 1) : 0);
}
}
function isPeak(i) {
if (i <= 0 || i >= nums.length - 1) return false;
return nums[i] > nums[i - 1] && nums[i] > nums[i + 1];
}
const n = nums.length;
const bit = new BIT(n);
const peaks = new Array(n).fill(false);
for (let i = 1; i < n - 1; i++) {
if (isPeak(i)) {
peaks[i] = true;
bit.update(i, 1);
}
}
const result = [];
for (const query of queries) {
if (query[0]
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 预处理 | O(n log n) | O(n) |
| 单次查询 | O(log n) | O(1) |
| 单次修改 | O(log n) | O(1) |
| 总时间复杂度 | O((n + m) log n) | O(n) |
其中 n 为数组长度，m 为查询数量。树状数组的空间复杂度为 O(n)，时间复杂度为单次操作 O(log n)。