題目描述：

/**
戰(zhàn)爭游戲的至關(guān)重要環(huán)節(jié)就要到來了，
這次的結(jié)果將決定王國的生死存亡，小B負(fù)責(zé)首都的防衛(wèi)工作。
首都位于一個(gè)四面環(huán)山的盆地中，周圍的n個(gè)小山構(gòu)成一個(gè)環(huán)，
作為預(yù)警措施，小B計(jì)劃在每個(gè)小山上設(shè)置一個(gè)觀察哨，日夜不停的瞭望周圍發(fā)生的情況。
 一旦發(fā)生外地入侵事件，山頂上的崗哨將點(diǎn)燃烽煙，
 若兩個(gè)崗哨所在的山峰之間沒有更高的山峰遮擋且兩者之間有相連通路，
 則崗哨可以觀察到另一個(gè)山峰上的烽煙是否點(diǎn)燃。
 由于小山處于環(huán)上，任意兩個(gè)小山之間存在兩個(gè)不同的連接通路。
 滿足上述不遮擋的條件下，一座山峰上崗哨點(diǎn)燃的烽煙至少可以通過一條通路被另一端觀察到。
 對于任意相鄰的崗哨，一端的崗哨一定可以發(fā)現(xiàn)一端點(diǎn)燃的烽煙。
小B設(shè)計(jì)的這種保衛(wèi)方案的一個(gè)重要特性是能夠觀測到對方烽煙的崗哨對的數(shù)量，
她希望你能夠幫她解決這個(gè)問題。
輸入描述:
輸入中有多組測試數(shù)據(jù)，
每一組測試數(shù)據(jù)的第一行為一個(gè)整數(shù)n(3<=n<=10^6),為首都周圍的小山數(shù)量，
第二行為n個(gè)整數(shù)，依次表示為小山的高度h（1<=h<=10^9）.
輸出描述:
對每組測試數(shù)據(jù)，在單獨(dú)的一行中輸出能相互觀察到的崗哨的對數(shù)。
輸入例子1:
5
1 2 4 5 3
輸出例子1:
7
*/

思路如下：
把數(shù)組shift然后得到最高的放在最左
1 2 4 5 3 變成 5 3 1 2 4
使用嚴(yán)格遞減棧
?。?！注意?。?！
這里如果 5 5 5認(rèn)為兩兩都可以看到
用一個(gè)Node記錄一個(gè)遞減棧 Node.val記錄值
Node.freq記錄該值的入棧數(shù)

代碼如下：

#include<stdio.h>
#include<iostream>
#include<stack>
 
#define MAX_N 1000005
 
using namespace std;
 
struct Node{
    int val=-1, freq=0;
    Node(){}
    Node(int val){
        this->val=val;
        this->freq=1;
    }
    Node(const Node& node){
        this->val=node.val;
        this->freq=node.freq;
    }
};
 
int arr1[MAX_N], arr2[MAX_N];
 
int main()
{
    int N, maxIdx=-1, maxH=-1;
    scanf("%d", &N);
    for(int i=0; i<N; i++)
        scanf("%d", arr1+i);
    for(int i=0; i<N; i++){
        if(arr1[i]>maxH){
            maxH=arr1[i];
            maxIdx=i;
        }
    }
    //把a(bǔ)rr1最高放在arr2的最左邊，實(shí)現(xiàn)arr1的shift
    for(int i=0; i<N; i++){
        arr2[i]=arr1[maxIdx];
        maxIdx=(maxIdx+1)%N;
    }
    //根據(jù)arr2做遞減棧
    long long total=0;
    stack<Node> st;
    st.push(Node(arr2[0]));
    for(int i=1; i<N; i++){
        if(arr2[i]==st.top().val){
            st.top().freq++;
        }
        else if(arr2[i]<st.top().val){
            st.push(Node(arr2[i]));
        }
        else{
            //arr2[i]>st.top().val
            while(!st.empty() && arr2[i]>st.top().val){
                //加上top這個(gè)節(jié)點(diǎn)，相同高度兩兩可以看到的情況
                total+=((long long)st.top().freq*(long long)(st.top().freq-1)/2);
                //由于st的最左邊節(jié)點(diǎn)一定是最高的，不可能為空
                //當(dāng)前st.top這個(gè)高度 可以與兩段更高的段組成2*st.top.freq對
                total+=(2*st.top().freq);
                st.pop();
            }
            if(!st.empty() && arr2[i]==st.top().val){
                st.top().freq++;
            }
            else{
                st.push(Node(arr2[i]));
            }
        }
    }
    //此時(shí)如果st還沒有空的話，那么就是一圈從左到右嚴(yán)格遞減的段, 或者只有一段
    //如剩下 555 444 33
    while(!st.empty()){
         //加上top這個(gè)節(jié)點(diǎn)，相同高度兩兩可以看到的情況
         int curFreq=st.top().freq;
         total+=((long long)curFreq*(long long)(curFreq-1)/2);
         st.pop();
         //若此時(shí)st還不空，那么左邊可以看到當(dāng)前這個(gè)
         if(!st.empty()){
            //當(dāng)前左邊至少還有兩個(gè)
            if(st.size()>1){
                //當(dāng)前的節(jié)點(diǎn)可以被左邊第一個(gè)看到，和最高的節(jié)點(diǎn)向左看到(一個(gè)環(huán))
                total+=(2*curFreq);
            }
            else{
                //其實(shí)當(dāng)前這個(gè)節(jié)點(diǎn)左邊第一個(gè)就是最高的節(jié)點(diǎn)了，這最高節(jié)點(diǎn)的最右邊一個(gè)山峰可以看到curFreq
                total+=curFreq;
                //若最高的節(jié)點(diǎn)大于2個(gè)那么，最高節(jié)點(diǎn)的最左一個(gè)山峰還能再看一次當(dāng)前這個(gè)節(jié)點(diǎn)
                if(st.top().freq>1){
                    total+=curFreq;
                }
            }
         }
    }
    printf("%lld", total);
    return 0;
}