企业官网建设流程全解析

数组中的沉默元素计数

阿里研发岗 0530笔试 第一题

题目内容

TkTkTk有一个长度为nnn的数组 {a1,a2,…,ana_1, a_2, …, a_na1​,a2​,…,an​}，对于下标满足1<i<n1 < i < n1<i<n的元素aia_iai​，若其左侧所有元素的最大值到它的距离，等于其右侧所有元素的最大值到它的距离，那么这个数字就是沉默的。若左侧（或右侧）区域存在多个数值相等的最大值，则选择其中与iii距离最近的下标计算距离。
TkTkTk想知道数组中一共有多少位置不同的沉默的数字，请输出这个值。

输入描述

每个测试文件均包含多组测试数据。

• 第一行输入一个整数T(1≤T≤104)T(1 ≤ T ≤ 10^4)T(1≤T≤104)，代表数据组数。
• 每组测试数据描述如下：

1. 第一行输入一个整数n(3≤n≤2×105)n(3 ≤ n ≤ 2 × 10^5)n(3≤n≤2×105)，表示数组长度。
2. 第二行输入nnn个整数a1,a2,…,an（1≤ai≤109)a_1, a_2, …, a_n（1 ≤ a_i ≤ 10^9)a1​,a2​,…,an​（1≤ai​≤109)，表示数组a。

• 保证单个测试文件的nnn之和不超过2×1052 × 10^52×105。

输出描述

对于每一组测试数据，新起一行，输出一个整数表示结果。

样例1

输入

2 3 1 1 1 5 1 4 4 5 2

输出

1 2

题解和思路

思路

实现思路：模拟

1. 定义left和right分别记录当前元素位置左侧最大值位置和右侧最大值位置。、
2. 计算left和right对应值，以left为例，定义maxValue = -1和maxValueIndex = -1分贝表示对应侧最大值和对应位置，从前往后进行遍历，对于位置i的处理逻辑如下：
   • 如果maxValueIndex != -1, 更新left[i] = maxValueIndex
   • 尝试更新maxValueIndex, 如果a[i] >= maxValue, 更新maxValueIndex = i , maxValue = a[i]

• 统计每组沉默数字，从前往后遍历如果abs(i - left[i]) == abs(i - right[i])对应沉默数字+1.前提left[i] != -1 and right[i] != -1

C++

#include<bits/stdc++.h>usingnamespacestd;intmain(){ios_base::sync_with_stdio(false);cin.tie(nullptr);intT;cin>>T;while(T--){intn;cin>>n;vector<int>a(n);for(inti=0;i<n;i++){cin>>a[i];}// 记录左侧最大值位置vector<int>left(n,-1);// 记录右侧最大值位置vector<int>right(n,-1);// 处理左侧intmaxValue=-1;intmaxValueIndex=-1;for(inti=0;i<n;i++){intval=a[i];if(maxValueIndex!=-1){left[i]=maxValueIndex;}if(maxValue<=val){maxValue=val;maxValueIndex=i;}}// 处理右侧maxValue=-1;maxValueIndex=-1;for(inti=n-1;i>=0;i--){intval=a[i];if(maxValueIndex!=-1){right[i]=maxValueIndex;}if(maxValue<=val){maxValue=val;maxValueIndex=i;}}intcount=0;for(inti=0;i<n;i++){if(left[i]==-1||right[i]==-1){continue;}if(abs(i-left[i])==abs(i-right[i])){count++;}}cout<<count<<endl;}return0;}

Java

importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intT=sc.nextInt();while(T-->0){intn=sc.nextInt();int[]a=newint[n];for(inti=0;i<n;i++){a[i]=sc.nextInt();}// 记录左侧最大值位置int[]left=newint[n];Arrays.fill(left,-1);// 记录右侧最大值位置int[]right=newint[n];Arrays.fill(right,-1);// 处理左侧intmaxValue=-1;intmaxValueIndex=-1;for(inti=0;i<n;i++){intval=a[i];if(maxValueIndex!=-1){left[i]=maxValueIndex;}if(maxValue<=val){maxValue=val;maxValueIndex=i;}}// 处理右侧maxValue=-1;maxValueIndex=-1;for(inti=n-1;i>=0;i--){intval=a[i];if(maxValueIndex!=-1){right[i]=maxValueIndex;}if(maxValue<=val){maxValue=val;maxValueIndex=i;}}intcount=0;for(inti=0;i<n;i++){if(left[i]==-1||right[i]==-1){continue;}if(Math.abs(i-left[i])==Math.abs(i-right[i])){count++;}}System.out.println(count);}}}

python

t=int(input())for_inrange(t):n=int(input())a=list(map(int,input().split()))# 记录左侧最大值位置left=[-1]*n# 记录右侧最大值位置right=[-1]*n# 处理左侧max_value=-1max_value_index=-1foriinrange(n):val=a[i]ifmax_value_index!=-1:left[i]=max_value_indexifmax_value<=val:max_value=val max_value_index=i# 处理右侧max_value=-1max_value_index=-1foriinrange(n-1,-1,-1):val=a[i]ifmax_value_index!=-1:right[i]=max_value_indexifmax_value<=val:max_value=val max_value_index=i count=0foriinrange(n):ifleft[i]==-1orright[i]==-1:continueifabs(i-left[i])==abs(i-right[i]):count+=1print(count)

Javascript

constreadline=require('readline');constrl=readline.createInterface({input:process.stdin,output:process.stdout});constinput=[];rl.on('line',line=>{input.push(...line.trim().split(/\s+/).map(Number));});rl.on('close',()=>{letidx=0;letT=input[idx++];while(T--){constn=input[idx++];consta=[];for(leti=0;i<n;i++){a.push(input[idx++]);}// 记录左侧最大值位置constleft=newArray(n).fill(-1);// 记录右侧最大值位置constright=newArray(n).fill(-1);// 处理左侧letmaxValue=-1;letmaxValueIndex=-1;for(leti=0;i<n;i++){constval=a[i];if(maxValueIndex!==-1){left[i]=maxValueIndex;}if(maxValue<=val){maxValue=val;maxValueIndex=i;}}// 处理右侧maxValue=-1;maxValueIndex=-1;for(leti=n-1;i>=0;i--){constval=a[i];if(maxValueIndex!==-1){right[i]=maxValueIndex;}if(maxValue<=val){maxValue=val;maxValueIndex=i;}}letcount=0;for(leti=0;i<n;i++){if(left[i]===-1||right[i]===-1){continue;}if(Math.abs(i-left[i])===Math.abs(i-right[i])){count++;}}console.log(count);}});

Go

packagemainimport("bufio""fmt""os")funcmain(){in:=bufio.NewReader(os.Stdin)varTintfmt.Fscan(in,&T)for;T>0;T--{varnintfmt.Fscan(in,&n)a:=make([]int,n)fori:=0;i<n;i++{fmt.Fscan(in,&a[i])}// 记录左侧最大值位置left:=make([]int,n)// 记录右侧最大值位置right:=make([]int,n)fori:=0;i<n;i++{left[i]=-1right[i]=-1}// 处理左侧maxValue:=-1maxValueIndex:=-1fori:=0;i<n;i++{val:=a[i]ifmaxValueIndex!=-1{left[i]=maxValueIndex}ifmaxValue<=val{maxValue=val maxValueIndex=i}}// 处理右侧maxValue=-1maxValueIndex=-1fori:=n-1;i>=0;i--{val:=a[i]ifmaxValueIndex!=-1{right[i]=maxValueIndex}ifmaxValue<=val{maxValue=val maxValueIndex=i}}count:=0fori:=0;i<n;i++{ifleft[i]==-1||right[i]==-1{continue}ifabs(i-left[i])==abs(i-right[i]){count++}}fmt.Println(count)}}funcabs(xint)int{ifx<0{return-x}returnx}