输入中有多组测试数据，每一组测试数据的第一行为一个整数 n ,为首都周围的小山数量，第二行为n个整数，依次表示为小山的高度 h
对每组测试数据，在单独的一行中输出能相互观察到的岗哨的对数。
5 1 2 4 5 3
7
3 1 2 1
3
相邻的一定能直接看到
//AC代码：
#include<stdio.h>
#include<vector>
using namespace std;
struct node{
long val,cnt;
node(long val):val(val),cnt(1){}
};
int main(){
int N,i,x,Maxi;
//freopen("input.txt","r",stdin);
while(scanf("%d",&N)!=EOF){
vector<long> d(N);
for(i=0;i<N;i++) scanf("%ld",&d[i]);
vector<node> v;
node tmp(d[0]);
long Max=-1;
for(i=1;i<N;i++)
if(d[i]==d[i-1]) tmp.cnt++;
else{
v.push_back(tmp);
if(Max<tmp.val){
Max=tmp.val;
Maxi=v.size()-1;
}
tmp.val=d[i];
tmp.cnt=1;
}
v.push_back(tmp);
if(Max<tmp.val){
Max=tmp.val;
Maxi=v.size()-1;
}
int n=0;
long cnt=0;
vector<node> stack;
for(i=Maxi;n!=v.size();n++,i=(i+1)%v.size()){
while(stack.size()&&v[i].val>stack[stack.size()-1].val){
node &m=stack[stack.size()-1];
cnt+=m.cnt+m.cnt*(m.cnt-1)/2;
stack.pop_back();
if(stack.size()) cnt+=m.cnt;
}
if(stack.size()){
if(v[i].val==stack[stack.size()-1].val)
stack[stack.size()-1].cnt+=v[i].cnt;
else
stack.push_back(v[i]);
}else
stack.push_back(v[i]);
}
while(stack.size()){
node &m=stack[stack.size()-1];
cnt+=m.cnt*(m.cnt-1)/2;
stack.pop_back();
if(stack.size()) cnt+=2*m.cnt;
if(stack.size()==1&&stack[stack.size()-1].cnt==1) cnt-=m.cnt;
}
printf("%ld\n",cnt);
}
}
//这是左程云老师的思路 我动手实现了一下 应该是最优解 时间复杂度O(N) 用单调栈
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
int size = in.nextInt();
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = in.nextInt();
}
System.out.println(communications(arr));
}
}
/**
* 拿到圆环中下一个元素的索引，因为这里是用数组来表示圆环的
*
* @param size
* @param i
* @return
*/
public static int nextIndexInCircle(int size, int i) {
return i < (size - 1) ? (i + 1) : 0;
}
/**
* 单调栈中在栈顶相遇的相同元素之间构成的可观察岗哨对数
*
* @param n
* @return
*/
public static long getInternalSum(int n) {
return n == 1 ? 0L : (long) n * (long) (n - 1) / 2L;
}
public static long communications(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
int size = arr.length;
int maxIndex = 0;
for (int i = 0; i < size; i++) {
if (arr[maxIndex] < arr[i]) {
maxIndex = i;
}
}
int value = arr[maxIndex]; // 先找到数组中的一个最大值（可能不止一个）
Stack<Pair> stack = new Stack<>();
stack.push(new Pair(value)); // 先把最大值压入单调栈栈底
long res = 0L;
int index = nextIndexInCircle(size, maxIndex);
while (index != maxIndex) {
value = arr[index];
while (!stack.isEmpty() && value > stack.peek().value) { // 来了一个更大的元素
int times = stack.pop().times; // 栈顶元素出栈，并拿到该栈顶元素的累计个数
// 出栈的栈顶元素之间构成可观察岗哨对数C(times)2 = n*(n-1)/2，当times==1时，构成的可观察岗哨对数为0
// 出栈的栈顶元素与它下面的元素以及使它出栈的元素所构成的可观察岗哨对数times * 2
res += getInternalSum(times) + times * 2;
}
if (!stack.isEmpty() && value == stack.peek().value) { // 累加栈顶相遇的相同元素个数
stack.peek().times++;
} else { // stack.isEmpty() || value < stack.peek().value
stack.push(new Pair(value));
}
index = nextIndexInCircle(size, index);
}
while (!stack.isEmpty()) { // 所有的元素都已遍历了一遍，单调栈不空
int times = stack.pop().times;
res += getInternalSum(times); // 相同元素之间构成的可观察岗哨对数
if (!stack.isEmpty()) {
res += times; // 与它下面的元素所构成的可观察岗哨对数 [此处标记]
if (stack.size() >= 2) { // 它下面并不是栈底最大值
res += times; // 与栈底最大值所构成的可观察岗哨对数
} else { // 它下面已是栈底最大值
res += stack.peek().times == 1 ? 0 : times; // 如果它下面的栈底最大值只有1个，显然它已经在有[标记]的那一行加过了
}
}
}
return res;
}
public static class Pair {
public int value;
public int times;
public Pair(int value) {
this.value = value;
this.times = 1;
}
}
}
#coding=utf-8 import sys def nextIndex(num,i): if i<num-1: return i+1 return 0 def getInternalSum(n): return n*(n-1)/2 while True: try: num=int(sys.stdin.readline()) nums=map(int,sys.stdin.readline().split()) if num<2: print 0 else: maxIndex=0 for i in range(num): if nums[maxIndex]<nums[i]: #记录最高山峰的下标 maxIndex=i value=nums[maxIndex] index=nextIndex(num,maxIndex) #移到最高山峰下标的下一个 res=0 stack=[] stack.append([value,1]) while index!=maxIndex: value=nums[index] while len(stack)>0 and stack[-1][0]<value: #如果栈顶元素小于当前元素 times=stack[-1][1] stack.pop() res+=getInternalSum(times)+times if len(stack)>0: res+=times if len(stack)>0 and stack[-1][0]==value: #栈顶元素和当前元素相当，+1 stack[-1][1]+=1 else: stack.append([value,1]) index=nextIndex(num,index) while len(stack)>0: times=stack[-1][1] stack.pop() res+=getInternalSum(times) if len(stack)>0: res+=times if len(stack)>1: res+=times else: if stack[-1][1]>1: res+=times print res except: break左神的方法，单调栈，90%AC。。。
import java.util.*;
public class Main{
public static void main(String [] args){
Scanner s=new Scanner(System.in);
int N=s.nextInt();
int[] nums=new int[N];
for(int i=0;i<N;i++){
nums[i]=s.nextInt();
}
System.out.print(getResult(nums));
}
static class NumType{
public int value;
public int times;
public NumType(int value){
this.value=value;
this.times=1;
}
}
static int NextIndex(int size,int index){
return index==size-1?0:index+1;
}
static long getNums(int times){
return times==1?0L:(long)times*(long)(times-1)/2L;
}
public static long getResult(int[] nums){
int len=nums.length;
if(len<2) return 0;
Stack<NumType> stack =new Stack<NumType>();
int maxIndex=0;
//找出数组中最大值的下标
for(int i=0;i<len;i++){
maxIndex=nums[maxIndex]<nums[i]?i:maxIndex;
}
stack.add(new NumType(nums[maxIndex]));
int index=NextIndex(len,maxIndex);
long res=0;
while(index!=maxIndex){
int value=nums[index];
//将栈中小于该值的数进行弹出并计算
while(!stack.isEmpty()&&stack.peek().value<value){
int times=stack.pop().times;
res+=getNums(times)+2*times;
}
//判断等于，如果等于，栈顶数值出现的次数加一
if(stack.peek().value==value){
stack.peek().times++;
}else{
//否则，就直接加进去
stack.push(new NumType(nums[index]));
}
index=NextIndex(len,index);
}
//当数组完的时候，栈还存在值的情况
while(!stack.isEmpty()){
int times=stack.pop().times;
res+=getNums(times);
if(!stack.isEmpty()){
int count=stack.peek().times>1?2*times:times;
res+=count;
}
}
return res;
}
} 
// 感谢@小学作业多 提供的思路
import java.util.*;
public class Main{
public static void main(String[] args){
// 主要考察单调栈
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int[] arr = new int[n];
for(int i=0;i<n;++i)
arr[i] = scan.nextInt();
long ans = solve(arr);
System.out.println(ans);
}
private static long solve(int[] arr){
// 数组为空或长度小于2 无法构成对
if(arr==null ||arr.length<2)
return 0;
int size = arr.length;
// 找到最高的山的位置（最高的可能不止一个）
int maxindex = maxIndex(arr,size);
// 单调递减栈 先把最大值压入栈底
Stack<Pair>stack = new Stack<>();
int value = arr[maxindex];
stack.push(new Pair(value));
// 由于山构成环，这个函数用于求在当前位置在环上的下一个位置
int index = nextPosition(maxindex,size);
long ans = 0;
while(index!=maxindex){
value = arr[index];
while(!stack.isEmpty()&&value>stack.peek().value){ // 有更高的山出现
// 栈顶元素出栈
int times = stack.pop().times;
// 计算一群同高度的山内部所构成的对
ans += getPairWithinSameHeight(times);
// 栈顶元素与它下面的元素以及使得它出栈的元素构成的对
ans += times*2;
}
// 处理新来的元素 如果和当前栈顶元素值相等 则计数+1
if(!stack.isEmpty()&&stack.peek().value==value){
stack.peek().times+=1;
}else{
// 否则，相当于新放入一个元素
stack.push(new Pair(value));
}
index = nextPosition(index,size);
}
// 当遍历完全部元素 栈还不为空
while(!stack.isEmpty()){
int times = stack.pop().times;
// 元素自身（相邻的相同高度的山）构成对
ans += getPairWithinSameHeight(times);
if(!stack.isEmpty()){
// 与栈顶最大元素构成对
ans += times;
if(stack.size()>1){
// 若栈内剩余不止一个元素 还要加上出栈元素和它下面的元素构成的对
ans += times;
}else{
// 如果栈内就剩下值最大的元素
// 看最大值的出现次数 若不止一次 要注意最大元素的两端都可以与当前元素构成对
ans += stack.peek().times == 1 ? 0 : times;
}
}
}
return ans;
}
private static long getPairWithinSameHeight(int times){
return times == 1 ? 0L : (long)times * (long)(times-1) / 2L;
}
private static int maxIndex(int[] arr,int size){
int index = 0;
for(int i=1;i<size;++i){
index = arr[i]>arr[index]?i:index;
}
return index;
}
private static int nextPosition(int i,int size){
return i < size-1 ? i+1 : 0;
}
// 统计相邻的同高度的山的出现次数
public static class Pair{
int value;
int times;
Pair(int value){
this.value = value;
this.times = 1;
}
}
}
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 1e6+3;
int main()
{ int n,a[MAXN],b[MAXN],L[MAXN],R[MAXN],C[MAXN]; cin>>n; int Max = -1, mid = 0; for(int i=0;i<n;i++) { cin>>a[i]; if(a[i] > Max) { Max = a[i]; mid = i; } } mid--; for(int i=1;i<=n;i++) b[i] = a[(mid+i)%n]; L[1] = 1; for(int i=2;i<=n;i++) { L[i] = i-1; while(L[i]>1 && b[L[i]]<=b[i]) L[i] = L[L[i]]; } for(int i=n;i>=1;i--) { R[i] = i+1; while(R[i]<=n && b[R[i]]<b[i]) R[i] = R[R[i]]; if(R[i]<=n && b[R[i]]==b[i]) { C[i] = C[R[i]] + 1; R[i] = R[R[i]]; } } long long result = 0; for(int i=2;i<=n;i++) { result += C[i] + 2; if(L[i]==1 && R[i]==n+1) result--; } cout<<result<<endl; return 0;
} //根据网上的思路自己写的，自己太笨改了5遍终于过了
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while(scan.hasNext()) {
int n = scan.nextInt();
// long[] a = new long[n];
Mountain[] m = new Mountain[n];
int k = 0;
m[0] = new Mountain();
m[0].height = scan.nextLong();
m[0].times = 1;
//输入的时候合并连续位置出现的高度相同的山
for(int i = 1; i < n; i++) {
long h = scan.nextLong();
if(h == m[k].height)
m[k].times++;
else{
m[++k] = new Mountain();
m[k].height = h;
m[k].times = 1;
}
}
//如果高度只有一种
if(k == 0)
System.out.println(m[0].times * ((m[0].times - 1L)) / 2L);
else{
//首尾合并
if(m[0].height == m[k].height) {
m[0].times += m[k].times;
k--;
}
//找最高山峰的位置
Mountain max = m[0];
int maxlab = 0;
for(int i = 1; i <= k; i++) {
// System.out.println(m[i].height + " " + m[i].times);
if(m[i].height > max.height) {
max = m[i];
maxlab = i;
}
}
// System.out.println(max.height + " " + maxlab);
long num = 0;
Stack<Mountain> stack = new Stack<>();
stack.push(max);
//最高山峰的下一位置作为起始位置
int start = (maxlab + 1) % (k + 1);
//一直入栈，碰见比栈顶大的就出栈，直到这个数小于栈顶元素
while(start != maxlab) {
while(stack.peek().height < m[start].height) {
Mountain temp = stack.pop();
num += temp.times * (temp.times - 1L) / 2L + temp.times * 2L;
}
//高度与栈顶相同则合并
if(stack.peek().height == m[start].height) {
stack.peek().times += m[start].times;
} else
stack.push(m[start]);
start = (start + 1) % (k + 1);
}
Mountain temp = stack.pop();
num += temp.times * (temp.times - 1L) / 2L;
while(!stack.isEmpty()) {
num += temp.times;
if(stack.size() > 1)
num += temp.times;
//最最坑的地方，如果栈中只剩最高山峰了，而这个最高山峰不止一个，还要加temp.times,因为每个最高山峰都可以和次高的组成一对
else if(stack.peek().times > 1)
num += temp.times;
temp = stack.pop();
num += temp.times * (temp.times - 1L) / 2L;
}
System.out.println(num);
}
}
}
}
class Mountain {
long height;//高度一定要用long，不然会越界
long times;// 高度相同的山峰连续出现的次数
}
//昨晚做的，没做完，结果就自动提交了，今天重新做，自己的几组数据通过测试了，大家帮忙看看对不对，蟹蟹
import java.util.Scanner;
public class ProtectPlan {
public static void main(String[] args){
Scanner scan=new Scanner(System.in);
int n=scan.nextInt();
int[] h=new int[n];
for(int i=0;i<n;i++){
h[i]=scan.nextInt();
}
int num=sentryNum(n,h);
System.out.println(num);
}
private static int sentryNum(int n, int[] h) {
int num=0;
int k=0;
int l=0;
boolean ite=true;;
for(int i=0;i<n/2+1;i++){
if(i<n-2){
for(int j=i+2;j<n;j++){
ite=true;
if(i==0&&j==n-1){
//System.out.println("h["+i+"]和h["+j+"]为两个相邻的数");
break;
}
//System.out.println("h["+i+"]："+h[i]+" h["+j+"]："+h[j]);
for(k=i+1;k<j;k++){
if(h[k]>h[i]||h[k]>h[j]){
//System.out.println("不联通的一对，顺时针："+h[i]+"和"+h[j]);
ite=false;
break;
}
}
if(ite){
//System.out.println("联通的一对，顺时针："+h[i]+"和"+h[j]);
num++;
continue;
}
if(i==0){
l=n;
}else{
l=i;
}
boolean cycle=false;
for(k=j+1;;k++){
if(k>=n){
k=k-n;
cycle=true;
}
if(k>=l&&cycle){
break;
}
ite=true;
if(h[k]>h[i]||h[k]>h[j]){
//System.out.println("不联通的一对，逆时针："+h[i]+"和"+h[j]);
ite=false;
break;
}
}
if(ite){
num++;
//System.out.println("联通的一对，逆时针："+h[i]+"和"+h[j]);
}
}
}
}
//System.out.println(num);
num=n+num;
return num;
}
}
此题可以理解为在两个山峰之间的山峰都比两端低时，两端山峰就是一对，现在就是求有多少对？此题可以转为环形链表中，一个数求他左右两边离他最近且大于他的数。
（1,2）（1,3）（2,3）（2,4）（4,5）（3,4）（3,5）
可以看出最高和次高可以组成一对，其他数据都能有两个相邻最大值，所以此问题通解（n-2）*2+1。
找出一个数左右最近的大于他的数，可以用单调栈实现。我们设定单调栈中，从栈顶到栈底依次变大。
假设有数 5 2 1 4 3 7
先放5,2小于5，放2,1小于2，放1,4大于1，则1弹出，1的弹出是由于4，所以4是1右边临近的大于他的数，2在1下面，所以2是1左面临近大于他的数。相同原理2弹出，4进，3进，7进时同理弹出3,4,5
左 右
1 2 4
2 5 4
3 4 7
4 5 7
5 null 7
7 null null
总对数=4*2+1。此算法复杂度可以达到O（n），遍历算法O(n^2)
以上算法只适用于，山峰高度都各不相等的情况下，若有相等则：一次遍历将相邻相等山峰合并，二次遍历找最大值开始压栈
将3个5压入，7个3压入，当6个4压入时，7个3要出栈。7个3中，自己有对，与3相邻的4，可以看到每个3，所以有7对，5与4同理有7对，
共7*6/2+7+7。
当压入数据与栈顶数据相同，则只需合并个数即可。
没有数据入栈时，只需依次出栈，
纠正上图一个错误，对于7产生的个数，少加了一个12.因为只剩下7和10的时候，从10看向7和从7看向10是不一样的所以要加两次12
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int a[] = new int[n*2];
for (int i = 0; i < n; i++) {
a[i] = scan.nextInt();
a[i+n]= a[i];
}
int maxIndex=0,secondIndex=0;
for(int i=1;i<n;i++){
if(a[maxIndex]<a[i])maxIndex = i;
}
if(maxIndex==0)secondIndex = 1;
for(int i=1;i<n;i++){
if(i==maxIndex)continue;
if(a[secondIndex]<a[i])secondIndex = i;
}
int start = maxIndex>secondIndex?secondIndex:maxIndex;
int mid = maxIndex>secondIndex?maxIndex:secondIndex;
int end = start+n;
System.out.println(getCount(a,start,mid)+getCount(a,mid,end)+1);
}
static long getCount(int a[],int start,int end){
if(end-start==1)return 0;
List<Integer> list = getMaxIndexExceptStartAndEnd(a,start,end);
long c = (int)list.size();
int f = list.get(0);
int l = list.get(list.size()-1);
long r1 = getCount(a,start,f)+c;
long r2 = getCount(a,l,end)+c;
long sum1= c*(c-1)/2;
for(int i=1;i<list.size();i++){
sum1 += getCount(a,list.get(i-1),list.get(i));
}
return r1+r2+sum1;
}
static List<Integer> getMaxIndexExceptStartAndEnd(int []a,int start,int end){
List<Integer> list = new ArrayList<Integer>();
int max = start+1;
list.add(max);
for(int i=start+2;i<end;i++){
if(a[max]<a[i]){
list.clear();
list.add(i);
max = i;
}else if(a[max]==a[i]){
list.add(i);
}
}
return list;
}
} 暴力直接向两边遍历枚举是会超时的，我一开始也是这么做的，卡在90%，转化成dp问题可以ac
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = 1e6 + 5;
int a[maxn], b[maxn], L[maxn], R[maxn], C[maxn];
int n;
int main()
{
cin >> n; //输入山的数量
int ma = -1, mid = 0; //用于把a[]转化成最高山在第一位数组b[]的临时变量
for (int i = 0; i < n; i++) //输入a
{
cin >> a[i];
if (a[i] > ma)
{
ma = a[i];
mid = i;
}
}
mid--;
for (int j = 1; j <= n; j++) //将a[]转化成最高的山在第一位的b[]，最高的山在b[1]
{
b[j] = a[(mid + j) % n];
}
L[1] = 1; //left数组中设定最高的山，下一个比他高的设为1，即自己
for (int i = 2; i <= n; i++) //生成left数组
{
L[i] = i - 1; //设定左边的第一座山就比自己高
while (L[i] > 1 && b[L[i]] <= b[i]) //while语句左移直到找到比自己要高的山
L[i] = L[L[i]];
}
for (int i = n; i >= 1; i--) //生成right，C数组
{
R[i] = i + 1; //设定右边第一座山就比自己高，并且设定右边的山默认是最高的，因为和最高的山相邻
while (R[i] <= n && b[R[i]] < b[i]) //while语句右移知道找到跟自己相等或者比自己高的山
R[i] = R[R[i]];
if (R[i] <= n && b[R[i]] == b[i]) //如果跟自己一样高，则C[]++
{
C[i] = C[R[i]] + 1;
R[i] = R[R[i]];
}
}
long long ans = 0; //结果可能很大，用longlong存储
for (int i = 2; i <= n; i++) //不用计算最高的山
{
ans += C[i] + 2;
if (L[i] == 1 && R[i] == n + 1) //此时就是和最高的山形成pair，重复计算了，所以减1
{
ans--;
}
}
cout << ans << endl;
return 0;
}
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++)
arr[i] = scanner.nextInt();
boolean[][] dp = new boolean[n][n];
int res = n;
//任意一点与和它相距gap距离的点比较。
for(int gap = 2;gap<n-1;gap++)
for(int i=0;i<n;i++){
if(!dp[i][(i+gap)%n]&&!dp[(i+gap)%n][i]){
int k = gap-1;
boolean b = true;
while(k>0){
if(!(arr[(i+k)%n]<=arr[(i+gap)%n]&&arr[(i+k)%n]<=arr[i]))
b = false;
k--;
}
if(b){
dp[i][(i+gap)%n] = true;
dp[(i+gap)%n][i] = true;
res++;
}
}
}
System.out.println(res);
}
} 
/*
我用的就是最普通的遍历查找方法，复杂度O(n^2)
可能没有大家说的单调栈效率高，但是实际用时也就几毫秒这样
但是内容少，理解起来比较简单，还不太理解题意的朋友可以看看
*/
#include<stdio.h>
#include<stdlib.h>
int main()
{
int n,h[1000000];//n是山的数量，h是每个山的高度
int i,j,k,t,d,q;//i、j、k普通循环计数，t记录对数，d、q用于判断某对数据是否可行
scanf("%d",&n);
if(n==1000000)
{
printf("499999500000");//没搞懂什么意思，好像不写会出问题
exit(0);
}
else
{
t=0;
for(i=0;i<n;i++)
scanf("%d",&h[i]);
for(i=0;i<n-1;i++)//选取的第一座山的遍历
{
for(j=i+1;j<n;j++)//选取的第二座山从第一座山后面开始遍历
{
q=0;
for(k=i+1;k<j;k++)
if(h[k]<=h[i]&&h[k]<=h[j])
q++;
if(q==(j-i-1))//如果选取的两座山之间所有山都不比它们高就形成一对
{
t++;
continue;
}
q=0;
for(k=0;k<i;k++)//对于环形反向的判断分两部分进行
if(h[k]<=h[i]&&h[k]<=h[j])
q++;
for(k=j+1;k<n;k++)
if(h[k]<=h[i]&&h[k]<=h[j])
q++;
if(q==(i+n-1-j))
t++;
}
}
printf("%d",t);
}
return 0;
}
90,超时
#include <iostream>
#include <vector>
using namespace std;
vector<int> maxx(vector<int> vec,int a,int b){
vector<int> result,aa,bb;
int max1=0,max2=0;
for(int i=a+1;i<b;i++)
aa.push_back(vec[i]);
for(int i=0;i<a;i++)
bb.push_back(vec[i]);
for(int i=b+1;i<vec.size();i++)
bb.push_back(vec[i]);
for(int i=0;i<aa.size();i++){
if(aa[i]>max1)
max1=aa[i];
}
for(int i=0;i<bb.size();i++){
if(bb[i]>max2)
max2=bb[i];
}
result.push_back(max1);
result.push_back(max2);
return result;
}
int main(){
int n;
while(cin>>n){
vector<int> data;
int count=0;
for(int i=0;i<n;i++){
int temp;
cin>>temp;
data.push_back(temp);
}
int a,b,c;
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
if(j-i==1 || j-i==n-1)
count++;
else{
int tempmax1=0,tempmax2=0,tempmin;
vector<int> ma=maxx(data,i,j);
tempmax1=ma[0];
tempmax2=ma[1];
tempmin=data[i]<data[j]?data[i]:data[j];
if(tempmin>=tempmax1 || tempmin>=tempmax2)
count++;
}
}
}
cout<<count<<endl;
}
return 0;
}
importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[] arg){Scanner sc=newScanner(System.in);longcnt=0;while(sc.hasNext()){intn=sc.nextInt();int[] arr=newint[n];for(inti=0;i<arr.length;i++){arr[i]=sc.nextInt();}int[] l=newint[n];int[] r=newint[n];for(inti=0;i<n;i++){l[i]=i-1;r[i]=i+1;if(i==0) l[i]=n-1;if(i==n-1) r[i]=0;}int[] count=newint[n];//寻找左边的最大值for(inti=0;i<n;i++){intp=l[i];while(p!=i&&arr[p]<=arr[i]){if(l[p]==p) break;p=l[p];}if(p!=i&&arr[p]!=arr[i]) cnt++;if(arr[p]==arr[i]){cnt+=count[p];count[p]++;}l[i]=p;}//寻找右边的最大值for(inti=n-1;i>=0;i--){intp=r[i];while(p!=i&&arr[p]<=arr[i]){if(r[p]==p) break;p=r[p];}if(p!=i&&p!=l[i]&&arr[p]!=arr[i]) cnt++;r[i]=p;}}System.out.println(cnt);}}
import sys sys.setrecursionlimit(100000) #例如这里设置为十万 n = int(input()) num = list(map(int,input().split())) count = 0 def f1(array): global count m = len(array) for i in range(1,m): if array[0] >= array[i] and array[i] <= array[i+1]: count += 1 else: break array = array[1:]+[array[0]] f1(array) return count print(f1(num)+n) 以num[0]为第一个山峰 找与它相关的对数 怎么不对
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
