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

福大大架构师每日一题

发布于 2025-01-19 20:11:09

3800

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

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[1]

题目来自leetcode3187。

大体步骤如下：

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 {
        return0
    }
    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>,
}

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

    fnupdate(&mutself, index: usize, value: i32) {
        letmut i = index asisize;
        while i < self.tree.len() asisize {
            self.tree[i asusize] += value;
            i += i & -i;
        }
    }

    fnpre(&self, index: usize) ->i32 {
        letmut res = 0;
        letmut i = index asisize;
        while i > 0 {
            res += self.tree[i asusize];
            i &= i - 1;
        }
        res
    }

    fnquery(&self, left: usize, right: usize) ->i32 {
        if right < left {
            return0;
        }
        self.pre(right) - self.pre(left - 1)
    }
}

fncount_of_peaks(nums: &mutVec<i32>, queries: Vec<Vec<i32>>) ->Vec<i32> {
    letn = nums.len();
    letmut f = Fenwick::new(n - 1);

    fnupdate_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);
            }
        }
    }

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

    letmut ans = Vec::new();

    forqin queries {
        if q[0] == 1 {
            ans.push(f.query((q[1] + 1) asusize, (q[2] - 1) asusize));
        } else {
            leti = q[1] asusize;
            forjinmax(i asisize - 1, 1) asusize..=min(i + 1, n - 2) {
                update_peak(&mut f, nums, j, -1);
            }
            nums[i] = q[2];
            forjinmax(i asisize - 1, 1) asusize..=min(i + 1, n - 2) {
                update_peak(&mut f, nums, j, 1);
            }
        }
    }

    ans
}

fnmain() {
    letmut nums = vec![4, 1, 4, 2, 1, 5];
    letqueries = vec![vec![2, 2, 4], vec![1, 0, 2], vec![1, 0, 4]];
    letresult = count_of_peaks(&mut nums, queries);
    println!("{:?}", result);
}

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

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

C完整代码如下：

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

typedefstruct {
    int *tree;
    int size;
} Fenwick;

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

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

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

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

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

voidupdate_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);
        }
    }
}

voidcount_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);
}

intmain() {
    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");

    return0;
}

C++完整代码如下：

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

usingnamespace std;

classFenwick {
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) {
            return0;
        }
        returnpre(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 (constauto &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;

    return0;
}

Python完整代码如下：

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

classFenwickTree:
    def__init__(self, size):
        self.size = size
        self.tree = [0] * (size + 1)  # 1-based index

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

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

    defquery(self, left, right):
        if right < left:
            return0
        returnself.prefix_sum(right) - self.prefix_sum(left - 1)


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


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


defcount_of_peaks(nums, queries):
    n = len(nums)
    fenwick_tree = FenwickTree(n - 1)
    
    # Initialize the Fenwick tree with the initial peak counts
    for i inrange(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 inrange(max(i - 1, 1), min(i + 1, n - 2) + 1):
                update_peak(fenwick_tree, nums, j, -1)
            nums[i] = query[2]
            for j inrange(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 = newArray(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) {
            return0;
        }
        returnthis.prefixSum(right) - this.prefixSum(left - 1);
    }
}

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

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

functioncountOfPeaks(nums, queries) {
    const n = nums.length;
    const fenwickTree = newFenwickTree(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); // 输出结果