解决leetcode第4017题数组中的峰值II

4017.数组中的峰值II难度困难问题描述给你一个长度为n的整数数组nums和一个二维整数数组queries。如果满足以下条件子数组nums[i..j]被称为峰值子数组其长度至少为3。存在一个下标k使得ikj且nums[k]nums[k-1]nums[k]nums[k1]你需要处理以下两种类型的查询[1,li,ri]计算完全包含在nums[li..ri]中的峰值子数组的数量。[2,indexi,vali]将nums[indexi]更新为vali。此更新适用于所有后续查询。返回一个数组answer其中answer[i]是按出现顺序排列的第i个类型1查询的答案。子数组是数组中连续的非空元素序列。示例1输入nums[1,3,2,4],queries[[1,0,3],[2,1,1],[1,0,3]]输出[2,0]解释查询[1,0,3][1,3,2]选择k1。则nums[k]3nums[k-1]1且nums[k1]2。因为31且32这是一个峰值子数组。[1,3,2,4]选择k1。则nums[k]3nums[k-1]1且nums[k1]2。因为31且32这是一个峰值子数组。查询[2,1,1]将nums[1]更新为1。数组变为[1,1,2,4]。查询[1,0,3]现在没有峰值子数组。因此answer[2,0]。示例2输入nums[9,8,9,8],queries[[1,1,3],[2,2,1],[1,0,2]]输出[1,0]解释查询[1,1,3]nums[1..3][8,9,8]选择k2。则nums[k]9nums[k-1]8且nums[k1]8。因为98且98这是一个峰值子数组。查询[2,2,1]将nums[2]更新为1。数组变为[9,8,1,8]。查询[1,0,2]没有峰值子数组。因此answer[1,0]。示例3输入nums[3,6,2,7,1],queries[[1,1,3],[2,3,0],[1,0,4]]输出[0,3]解释查询[1,1,3]唯一长度至少为3的子数组是[6,2,7]。其唯一可能的峰值下标是k2但nums[2]2小于nums[1]6和nums[3]7因此它不是一个峰值子数组。查询[2,3,0]将nums[3]更新为0。数组变为[3,6,2,0,1]。查询[1,0,4][3,6,2]选择k1。则nums[k]6nums[k-1]3且nums[k1]2。因为63且62这是一个峰值子数组。[3,6,2,0]选择k1。则nums[k]6nums[k-1]3且nums[k1]2。因为63且62这是一个峰值子数组。[3,6,2,0,1]选择k1。则nums[k]6nums[k-1]3且nums[k1]2。因为63且62这是一个峰值子数组。因此answer[0,3]。提示3nnums.length10**50nums[i]10**51queries.length10**5queries[i][1,li,ri]或queries[i][2,indexi,vali]0lirin-10indexin-10vali10**5分析问题解决下面几个小问题这道题也就迎刃而解了。一是对于一个数组先找出其中有多少个峰值把索引号0和峰值对应的索引号以及最后一个元素的索引号n-1以列表的形式返回如果中间没有峰值则返回空列表函数get_list_of_peak_index(nums1)实现这一功能二是对于只有一个峰值的数组nums2k[startpeakend]描述了一个查询如何把这个查询中的不同峰值子数组数量统计出来呢函数get_numbers_of_peak_sub_array(k,nums2)实现这一功能最后返回统计出来的峰值子数组数量t和不同的子数组列表temp三是处理第一种查询[1,li,ri]先根据查询取出对应的子数组然后查出子数组中的峰值列表把这个峰值对应的索引号列表比如[0,i1,i2,i3,......,in,n-1]分解成多个小部分[0,i1,i2]、[i1,i2,i3]、[i2,i3,i4]、......每一个部分只有一个峰值然后调用函数get_numbers_of_peak_sub_array(k,nums2)依次统计每个小部分中峰值子数组的数量最后将所有峰值子数组数量加起来就是这个查询对应的峰值子数组的总数量返回总数量和对应的峰值子数组列表temp四是处理第二种查询2,indexi,vali]函数get_changed_nums(query2,nums)实现了这一功能返回新的nums主程序根据查询序列queries依次取出查询调用相应的查询处理函数输出每次查询结果问题得到解决。程序如下#统计一个数组nums中峰值子数组的峰值索引号列表t并返回 def get_list_of_peak_index(nums1): t[0] nlen(nums1) for i in range(n-1): if nums1[i] nums1[i - 1] and nums1[i] nums1[i 1]: t.append(i) t.append(n-1) if len(t)3: return [] else: return t # 统计一个最大的峰值数组nums中峰值子数组的数量并返回 def get_numbers_of_peak_sub_array(k,nums2): nlen(nums2) startk[0] peakk[1] endk[2] t(peak-start)*(end-peak-1) temp[] for i in range(start,peak): for j in range(peak1,end): sub_arraynums2[i:j1] temp.append(sub_array) return t,temp #对查询[2,indexi,vali]的处理返回处理之后的nums def get_changed_nums(query2,nums): nums[query2[1]]query2[2] return nums #对查询[1,li,ri]的处理返回处理之后得到的完全包含其中的峰值子数组数量 def get_numbers_of_peak_subarray_by_query(query1,nums3): nums4nums3[query1[1]:query1[2]1] t get_list_of_peak_index(nums4) if not t: return 0,[] else: n 0 r len(t) temp[] for i in range(r - 2): a t[i] b t[i 1] c t[i 2] 1 k [a, b, c] m, e get_numbers_of_peak_sub_array(k, nums4) temp.extend(e) n m return n,temp #主程序 numseval(input(pls input nums)) queries eval(input(pls input queries)) t[] for query in queries: if query[0]1: n,aget_numbers_of_peak_subarray_by_query(query,nums) s有以下峰值子数组 if n!0 else 没有峰值子数组 print(f对于查询{query},{s}) if a: print(a) t.append(n) else: knums[::] numsget_changed_nums(query,nums) print(f对于查询{query},使得原数组{k}变为{nums}) print(answer ,t)运行实例一pls input nums[1,3,2,4]pls input queries[[1,0,3],[2,1,1],[1,0,3]]对于查询[1, 0, 3],有以下峰值子数组[[1, 3, 2], [1, 3, 2, 4]]对于查询[2, 1, 1],使得原数组[1, 3, 2, 4]变为[1, 1, 2, 4]对于查询[1, 0, 3],没有峰值子数组answer [2, 0]运行实例二pls input nums[9,7,9,7,9,2]pls input queries[[1,0,3],[2,1,10],[1,0,5]]对于查询[1, 0, 3],有以下峰值子数组[[9, 7, 9, 7], [7, 9, 7]]对于查询[2, 1, 10],使得原数组[9, 7, 9, 7, 9, 2]变为[9, 10, 9, 7, 9, 2]对于查询[1, 0, 5],有以下峰值子数组[[9, 10, 9], [9, 10, 9, 7], [9, 10, 9, 7, 9], [10, 9, 7, 9, 2], [9, 7, 9, 2], [7, 9, 2]]answer [2, 6]运行实例三pls input nums[3,6,2,7,1]pls input queries[[1,1,3],[2,3,0],[1,0,4]]对于查询[1, 1, 3],没有峰值子数组对于查询[2, 3, 0],使得原数组[3, 6, 2, 7, 1]变为[3, 6, 2, 0, 1]对于查询[1, 0, 4],有以下峰值子数组[[3, 6, 2], [3, 6, 2, 0], [3, 6, 2, 0, 1]]answer [0, 3]