2025-01-19：数组中的峰值。用go语言，在一个整数数组 nums 中，若某个元素大于其左右相邻的元素，则称该元素为“峰值”元素。

你会得到一个整数数组 nums 和一个二维数组 queries。需要处理两种操作：

1.queries[i] = [1, li, ri]：计算子数组 nums[li…ri] 中的峰值元素数量。

2.queries[i] = [2, indexi, vali]：将 nums[indexi] 的值更改为 vali。

最终，你需要返回一个数组 answer，其中依次包含了每一次第一种操作的结果。

请注意，子数组的第一个和最后一个元素不被视为峰值元素。

3 <= nums.length <= 100000。

1 <= nums[i] <= 100000。

1 <= queries.length <= 100000。

queries[i][0] == 1 或者 queries[i][0] == 2。

对于所有的 i ，都有：

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] <= 100000。

输入：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] 中的峰值元素。

答案2025-01-19：

chatgpt

题目来自leetcode3187。

大体步骤如下：

1.定义峰值：

• 一个元素 nums[i] 被认为是峰值元素，当且仅当 nums[i] 大于相邻的两个元素 nums[i-1] 和 nums[i+1]，即 nums[i] > nums[i-1] 且 nums[i] > nums[i+1]。

2.初始化 Fenwick Tree：

• 创建一个 Fenwick Tree (称为 f)，其大小为 n-1，用于存储可能的峰值数量。
• 在树的初始化阶段，遍历 nums 数组，检查 nums[i] 是否为峰值，若是，则在 Fenwick Tree 中更新相应的值。

3.查询操作：

• 当处理 queries[i] = [1, li, ri] 的查询时，使用 Fenwick Tree 的 query 方法计算 li 到 ri 的子数组中峰值的数量。
• 注意，只有子数组的 li 和 ri 之间的元素（不包括边界元素）将被视为可能的峰值。

4.更新操作：

• 当处理 queries[i] = [2, index, value] 的更新操作时，需要将 nums[index] 更新为 value。
• 在更新之前，需要检查 index 左边的 index-1 和右边的 index+1 元素是否会影响已有的峰值。如果 nums[index-1] 和 nums[index+1] 与 nums[index] 的新值不再符合峰值的条件，则在 Fenwick Tree 中对应减去峰值数量。
• 执行更新后，再次检查更新后的 nums[index-1] 和 nums[index+1]，如果新的值符合峰值条件，则在 Fenwick Tree 中对应增加峰值数量。

5.返回结果：

• 所有查询类型为 1 的结果将被存储在列表中，最后返回该列表作为输出。

时间复杂度

• 初始化阶段：遍历 nums 的长度为 n，每次更新 Fenwick Tree 最多需 O(log n) 的时间。初始化的时间复杂度为 O(n log n)。

• 每个查询操作（类型 1）：也是 O(log n)，因此如果有 q 个此类请求，总的时间复杂度是 O(q log n)。

• 更新操作（类型 2）同样是 O(log n)，因此如果有 q 个此类请求，总的时间复杂度也是 O(q log n)。

综上所述，综合处理所有的操作，总的时间复杂度为：O(n log n)+O(q log n)。

空间复杂度

• 使用了一个 Fenwick Tree 数组，大小为 n-1，因此额外空间复杂度为 O(n)。

• 由于我们只用了少量额外的变量，整体的空间复杂度依旧为 O(n)。

总结

• 时间复杂度：O(n log n + q log n)

• 空间复杂度：O(n)

Go完整代码如下：

package main

import (
	"fmt"
)

type fenwick []int

func (f fenwick) update(i, val int) {
	for ; i < len(f); i += i & -i {
		f[i] += val
	}
}

func (f fenwick) pre(i int) (res int) {
	for ; i > 0; i &= i - 1 {
		res += f[i]
	}
	return res
}

func (f fenwick) query(l, r int) int {
	if r < l {
		return 0
	}
	return f.pre(r) - f.pre(l-1)
}

func countOfPeaks(nums []int, queries [][]int) (ans []int) {
	n := len(nums)
	f := make(fenwick, n-1)
	update := func(i, val int) {
		if nums[i-1] < nums[i] && nums[i] > nums[i+1] {
			f.update(i, val)
		}
	}
	for i := 1; i < n-1; i++ {
		update(i, 1)
	}

	for _, q := range queries {
		if q[0] == 1 {
			ans = append(ans, f.query(q[1]+1, q[2]-1))
			continue
		}
		i := q[1]
		for j := max(i-1, 1); j <= min(i+1, n-2); j++ {
			update(j, -1)
		}
		nums[i] = q[2]
		for j := max(i-1, 1); j <= min(i+1, n-2); j++ {
			update(j, 1)
		}
	}
	return
}

func main() {
	nums := []int{4,1,4,2,1,5}
	queries := [][]int{{2,2,4},{1,0,2},{1,0,4}}
	result := countOfPeaks(nums,queries)
	fmt.Println(result)
}

Rust完整代码如下：

struct Fenwick {
    tree: Vec<i32>,
}

impl Fenwick {
    fn new(size: usize) -> Self {
        Fenwick {
            tree: vec![0; size + 1],
        }
    }

    fn update(&mut self, index: usize, value: i32) {
        let mut i = index as isize;
        while i < self.tree.len() as isize {
            self.tree[i as usize] += value;
            i += i & -i;
        }
    }

    fn pre(&self, index: usize) -> i32 {
        let mut res = 0;
        let mut i = index as isize;
        while i > 0 {
            res += self.tree[i as usize];
            i &= i - 1;
        }
        res
    }

    fn query(&self, left: usize, right: usize) -> i32 {
        if right < left {
            return 0;
        }
        self.pre(right) - self.pre(left - 1)
    }
}

fn count_of_peaks(nums: &mut Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
    let n = nums.len();
    let mut f = Fenwick::new(n - 1);

    fn update_peak(f: &mut Fenwick, nums: &[i32], i: usize, val: i32) {
        if i > 0 && i < nums.len() - 1 {
            if nums[i - 1] < nums[i] && nums[i] > nums[i + 1] {
                f.update(i, val);
            }
        }
    }

    for i in 1..(n - 1) {
        update_peak(&mut f, nums, i, 1);
    }

    let mut ans = Vec::new();

    for q in queries {
        if q[0] == 1 {
            ans.push(f.query((q[1] + 1) as usize, (q[2] - 1) as usize));
        } else {
            let i = q[1] as usize;
            for j in max(i as isize - 1, 1) as usize..=min(i + 1, n - 2) {
                update_peak(&mut f, nums, j, -1);
            }
            nums[i] = q[2];
            for j in max(i as isize - 1, 1) as usize..=min(i + 1, n - 2) {
                update_peak(&mut f, nums, j, 1);
            }
        }
    }

    ans
}

fn main() {
    let mut nums = vec![4, 1, 4, 2, 1, 5];
    let queries = vec![vec![2, 2, 4], vec![1, 0, 2], vec![1, 0, 4]];
    let result = count_of_peaks(&mut nums, queries);
    println!("{:?}", result);
}

// 輔助函數
fn max(a: isize, b: isize) -> isize {
    if a > b {
        a
    } else {
        b
    }
}

fn min(a: usize, b: usize) -> usize {
    if a < b {
        a
    } else {
        b
    }
}

C完整代码如下：

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int *tree;
    int size;
} Fenwick;

void fenwick_init(Fenwick *f, int size) {
    f->size = size + 1;  // 使用1-based索引
    f->tree = (int *)calloc(f->size, sizeof(int));
}

void fenwick_update(Fenwick *f, int index, int value) {
    for (; index < f->size; index += index & -index) {
        f->tree[index] += value;
    }
}

int fenwick_pre(Fenwick *f, int index) {
    int sum = 0;
    for (; index > 0; index &= index - 1) {
        sum += f->tree[index];
    }
    return sum;
}

int fenwick_query(Fenwick *f, int left, int right) {
    if (right < left) {
        return 0;
    }
    return fenwick_pre(f, right) - fenwick_pre(f, left - 1);
}

int is_peak(int *nums, int i) {
    return (nums[i - 1] < nums[i] && nums[i] > nums[i + 1]);
}

void update_peak(Fenwick *f, int *nums, int i, int val) {
    if (i > 0 && i < (f->size - 1)) {
        if (is_peak(nums, i)) {
            fenwick_update(f, i, val);
        }
    }
}

void count_of_peaks(int *nums, int n, int queries[][3], int query_count, int *result, int *result_count) {
    Fenwick f;
    fenwick_init(&f, n - 1);
    
    for (int i = 1; i < n - 1; i++) {
        update_peak(&f, nums, i, 1);
    }

    *result_count = 0;

    for (int q = 0; q < query_count; q++) {
        if (queries[q][0] == 1) {
            result[(*result_count)++] = fenwick_query(&f, queries[q][1] + 1, queries[q][2] - 1);
        } else {
            int i = queries[q][1];
            for (int j = (i > 1 ? i - 1 : 1); j <= (i < n - 2 ? i + 1 : n - 2); j++) {
                update_peak(&f, nums, j, -1);
            }
            nums[i] = queries[q][2];
            for (int j = (i > 1 ? i - 1 : 1); j <= (i < n - 2 ? i + 1 : n - 2); j++) {
                update_peak(&f, nums, j, 1);
            }
        }
    }
    
    free(f.tree);
}

int main() {
    int nums[] = {4, 1, 4, 2, 1, 5};
    int n = sizeof(nums) / sizeof(nums[0]);

    int queries[][3] = {{2, 2, 4}, {1, 0, 2}, {1, 0, 4}};
    int query_count = sizeof(queries) / sizeof(queries[0]);

    int result[query_count];
    int result_count;

    count_of_peaks(nums, n, queries, query_count, result, &result_count);

    for (int i = 0; i < result_count; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");

    return 0;
}

C++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Fenwick {
public:
    vector<int> tree;

    Fenwick(int size) {
        tree.resize(size + 1, 0); // 1-based index
    }

    void update(int index, int value) {
        for (; index < tree.size(); index += index & -index) {
            tree[index] += value;
        }
    }

    int pre(int index) {
        int sum = 0;
        for (; index > 0; index &= index - 1) {
            sum += tree[index];
        }
        return sum;
    }

    int query(int left, int right) {
        if (right < left) {
            return 0;
        }
        return pre(right) - pre(left - 1);
    }
};

void update_peak(Fenwick &f, vector<int> &nums, int i, int val) {
    if (i > 0 && i < nums.size() - 1) {
        if (nums[i - 1] < nums[i] && nums[i] > nums[i + 1]) {
            f.update(i, val);
        }
    }
}

vector<int> count_of_peaks(vector<int> &nums, vector<vector<int>> &queries) {
    int n = nums.size();
    Fenwick f(n - 1);

    for (int i = 1; i < n - 1; ++i) {
        update_peak(f, nums, i, 1);
    }

    vector<int> ans;

    for (const auto &q : queries) {
        if (q[0] == 1) {
            ans.push_back(f.query(q[1] + 1, q[2] - 1));
        } else {
            int i = q[1];
            for (int j = max(i - 1, 1); j <= min(i + 1, n - 2); ++j) {
                update_peak(f, nums, j, -1);
            }
            nums[i] = q[2];
            for (int j = max(i - 1, 1); j <= min(i + 1, n - 2); ++j) {
                update_peak(f, nums, j, 1);
            }
        }
    }
    return ans;
}

int main() {
    vector<int> nums = {4, 1, 4, 2, 1, 5};
    vector<vector<int>> queries = {{2, 2, 4}, {1, 0, 2}, {1, 0, 4}};
    
    vector<int> result = count_of_peaks(nums, queries);

    for (int res : result) {
        cout << res << " ";
    }
    cout << endl;

    return 0;
}

Python完整代码如下：

# -*-coding:utf-8-*-

class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.tree = [0] * (size + 1)  # 1-based index

    def update(self, index, value):
        while index <= self.size:
            self.tree[index] += value
            index += index & -index

    def prefix_sum(self, index):
        total = 0
        while index > 0:
            total += self.tree[index]
            index -= index & -index
        return total

    def query(self, left, right):
        if right < left:
            return 0
        return self.prefix_sum(right) - self.prefix_sum(left - 1)


def is_peak(nums, i):
    return nums[i - 1] < nums[i] > nums[i + 1]


def update_peak(fenwick_tree, nums, i, value):
    if 1 <= i < len(nums) - 1:
        if is_peak(nums, i):
            fenwick_tree.update(i, value)


def count_of_peaks(nums, queries):
    n = len(nums)
    fenwick_tree = FenwickTree(n - 1)
    
    # Initialize the Fenwick tree with the initial peak counts
    for i in range(1, n - 1):
        update_peak(fenwick_tree, nums, i, 1)

    results = []

    for query in queries:
        if query[0] == 1:
            results.append(fenwick_tree.query(query[1] + 1, query[2] - 1))
        else:
            i = query[1]
            for j in range(max(i - 1, 1), min(i + 1, n - 2) + 1):
                update_peak(fenwick_tree, nums, j, -1)
            nums[i] = query[2]
            for j in range(max(i - 1, 1), min(i + 1, n - 2) + 1):
                update_peak(fenwick_tree, nums, j, 1)

    return results


if __name__ == "__main__":
    nums = [4, 1, 4, 2, 1, 5]
    queries = [[2, 2, 4], [1, 0, 2], [1, 0, 4]]
    result = count_of_peaks(nums, queries)
    print(result)  # Output the results

JavaScript完整代码如下：

class FenwickTree {
    constructor(size) {
        this.size = size;
        this.tree = new Array(size + 1).fill(0); // 使用1-based索引
    }

    update(index, value) {
        for (let i = index; i <= this.size; i += i & -i) {
            this.tree[i] += value;
        }
    }

    prefixSum(index) {
        let sum = 0;
        for (let i = index; i > 0; i &= (i - 1)) {
            sum += this.tree[i];
        }
        return sum;
    }

    query(left, right) {
        if (right < left) {
            return 0;
        }
        return this.prefixSum(right) - this.prefixSum(left - 1);
    }
}

function isPeak(nums, i) {
    return nums[i - 1] < nums[i] && nums[i] > nums[i + 1];
}

function updatePeak(fenwick, nums, i, value) {
    if (i > 0 && i < nums.length - 1) {
        if (isPeak(nums, i)) {
            fenwick.update(i, value);
        }
    }
}

function countOfPeaks(nums, queries) {
    const n = nums.length;
    const fenwickTree = new FenwickTree(n - 1);

    for (let i = 1; i < n - 1; i++) {
        updatePeak(fenwickTree, nums, i, 1);
    }

    const results = [];

    for (let q of queries) {
        if (q[0] === 1) {
            results.push(fenwickTree.query(q[1] + 1, q[2] - 1));
        } else {
            const i = q[1];
            for (let j = Math.max(i - 1, 1); j <= Math.min(i + 1, n - 2); j++) {
                updatePeak(fenwickTree, nums, j, -1);
            }
            nums[i] = q[2];
            for (let j = Math.max(i - 1, 1); j <= Math.min(i + 1, n - 2); j++) {
                updatePeak(fenwickTree, nums, j, 1);
            }
        }
    }

    return results;
}

// 示例
const nums = [4, 1, 4, 2, 1, 5];
const queries = [[2, 2, 4], [1, 0, 2], [1, 0, 4]];
const result = countOfPeaks(nums, queries);
console.log(result); // 输出结果