题解 | #可见的山峰对数量(进阶)#

注意：刷该题目时，先做 单调栈结构 题目，会更好理解。

#include<iostream>
#include<vector>
#include<stack>
#include<map>
#include<limits>

using namespace std;
/* 类似pair,用于记录值和出现次数 */
class Record{
public:
    int val;
    int time;
    Record(int tval){
        val = tval;
        time = 1;
    }
};

class dNode{
public:
    int val;
    dNode* next;
    dNode* last;
};
/* 逆向列表类 */
class dList{
public:
    dNode* dhead;
    int n;
    dList(){
        dhead=NULL;
        int n=0;
    }
    /* 逆序类初始化 */
    void InitList();
};
/* 仅用于测试打印 */
void printdList(dNode* head){//顺时针打印
    dNode* cur=head;
    while(cur->next!=head){
        cout<<cur->val<<"-->";
        cur=cur->next;
    }
    cout<<cur->val<<endl;   
}
/* 从屁股后面开始创建，也可以从头开始创建顺序链表。 */
void dList::InitList(){
    dNode* cur=NULL,*left=NULL,*right=NULL;
    dNode* buttom=NULL;
    for(int i=0;i<n;i++){
        if(i==0){
            cur=new dNode;
            cin>>cur->val;
            cur->next=NULL;
            right=cur;
            buttom=cur;
            continue;
        }
        cur=new dNode;
        cin>>cur->val;
        cur->next=right;
        right->last=cur;
        right=cur;
    }
    dhead=cur;
    buttom->next=dhead;
    dhead->last=buttom;
    //printdList(dhead);
}
/* 找到最大值的位置 */
dNode* findMaxVal(dNode* src){
    dNode* ans=NULL;
    dNode* cur=src;
    int maxVal=INT16_MIN;
    while(cur->next!=src){
        if(cur->val>maxVal){
            maxVal=cur->val;
            ans=cur;
        }
        cur=cur->next;
    }
    if(cur->val>maxVal){
        maxVal=cur->val;
        ans=cur;
    }
    return ans;
}
/* 求解组合个数C，一劳永逸，以后刷题直接用 */
int Compandon(int total,int part){
    if(total<part)return total-1;
    if(total==part)return 1;
    map<int,bool> irecord;
    while(part){
        irecord.insert(pair<int,bool>(part,true));//under
        if(irecord.find(total)!=irecord.end()){
            irecord.erase(irecord.find(total));
        }else{
            irecord.insert(pair<int,bool>(total,false));//head
        }
        part--;
        total--;
    }
    double ans = 1;
    map<int,bool>::iterator itmap = irecord.begin();
    for(;itmap!=irecord.end();itmap++){
        if(itmap->second){
            ans=ans/(itmap->first);
        }else{
            ans=ans* (itmap->first);
        }
    }
    return (int)ans;
}
/* 主函数：
1、先找到最大值
2、从最大值开始沿着一个方向，创建单调栈结构,同时更新ansCount
3、清算结果。根据栈中数量个数进行计算
    a.如果剩最后一个（val,time），则只取time的组合数C(time,2)
    b.如果剩下两个就需要根据栈中最后一个last的time
        如果last.time>1,说明倒数第二个左右都有最大值
        否则，说明只有一边有最大值。
    其他，就按照组合数+time*2计算
    （tips:2是左右都有山就是2）
*/
int seeMon(int n,dNode* src){
    //cout<<"输入："<<endl;

    //printdList(src);

    dNode* MaxValIndex = findMaxVal(src);
    //cout<<MaxValIndex->val<<endl;
    stack<Record> sscord;
    sscord.push(Record(MaxValIndex->val));
    int ansCount=0;
    dNode* index= MaxValIndex->next;
    while(index!=MaxValIndex){
        if(index->val < sscord.top().val){
            sscord.push(Record(index->val));
        }else if(index->val == sscord.top().val){
            sscord.top().time++;
        }else if(index->val > sscord.top().val){
            Record trecord=sscord.top();sscord.pop();
            int ttime=trecord.time;
            ansCount += trecord.time*2+Compandon(ttime,2);
            continue;
        }
        index=index->next;
    }
    while(!sscord.empty()){
        if(sscord.size()==1){
            ansCount+=Compandon(sscord.top().time,2);
            sscord.pop();
        }else if(sscord.size()==2){
            Record lastTworecord=sscord.top();sscord.pop();
            if(sscord.top().time==1){
                ansCount+= lastTworecord.time + Compandon(lastTworecord.time,2);
            }else {
                ansCount+= lastTworecord.time*2 + Compandon(lastTworecord.time,2);
            }
        }else{
            ansCount+= sscord.top().time*2 + Compandon(sscord.top().time,2);
            sscord.pop();
        }
    }
    return ansCount;
}

int main(){
    dList dp;
    cin>>dp.n;
    dp.InitList();
    int count = seeMon(dp.n,dp.dhead);
    cout<<count<<endl;
    return 0;
}