笔试刷题-京东2018-07-23

题目描述：

/**
战争游戏的至关重要环节就要到来了，
这次的结果将决定王国的生死存亡，小B负责首都的防卫工作。
首都位于一个四面环山的盆地中，周围的n个小山构成一个环，
作为预警措施，小B计划在每个小山上设置一个观察哨，日夜不停的瞭望周围发生的情况。
 一旦发生外地入侵事件，山顶上的岗哨将点燃烽烟，
 若两个岗哨所在的山峰之间没有更高的山峰遮挡且两者之间有相连通路，
 则岗哨可以观察到另一个山峰上的烽烟是否点燃。
 由于小山处于环上，任意两个小山之间存在两个不同的连接通路。
 满足上述不遮挡的条件下，一座山峰上岗哨点燃的烽烟至少可以通过一条通路被另一端观察到。
 对于任意相邻的岗哨，一端的岗哨一定可以发现一端点燃的烽烟。
小B设计的这种保卫方案的一个重要特性是能够观测到对方烽烟的岗哨对的数量，
她希望你能够帮她解决这个问题。
输入描述:
输入中有多组测试数据，
每一组测试数据的第一行为一个整数n(3<=n<=10^6),为首都周围的小山数量，
第二行为n个整数，依次表示为小山的高度h（1<=h<=10^9）.
输出描述:
对每组测试数据，在单独的一行中输出能相互观察到的岗哨的对数。
输入例子1:
5
1 2 4 5 3
输出例子1:
7
*/

思路如下：
把数组shift然后得到最高的放在最左
1 2 4 5 3 变成 5 3 1 2 4
使用严格递减栈
！！！注意！！！
这里如果 5 5 5认为两两都可以看到
用一个Node记录一个递减栈 Node.val记录值
Node.freq记录该值的入栈数

代码如下：

#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;
        }
    }
    //把arr1最高放在arr2的最左边，实现arr1的shift
    for(int i=0; i<N; i++){
        arr2[i]=arr1[maxIdx];
        maxIdx=(maxIdx+1)%N;
    }
    //根据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这个节点，相同高度两两可以看到的情况
                total+=((long long)st.top().freq*(long long)(st.top().freq-1)/2);
                //由于st的最左边节点一定是最高的，不可能为空
                //当前st.top这个高度 可以与两段更高的段组成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]));
            }
        }
    }
    //此时如果st还没有空的话，那么就是一圈从左到右严格递减的段, 或者只有一段
    //如剩下 555 444 33
    while(!st.empty()){
         //加上top这个节点，相同高度两两可以看到的情况
         int curFreq=st.top().freq;
         total+=((long long)curFreq*(long long)(curFreq-1)/2);
         st.pop();
         //若此时st还不空，那么左边可以看到当前这个
         if(!st.empty()){
            //当前左边至少还有两个
            if(st.size()>1){
                //当前的节点可以被左边第一个看到，和最高的节点向左看到(一个环)
                total+=(2*curFreq);
            }
            else{
                //其实当前这个节点左边第一个就是最高的节点了，这最高节点的最右边一个山峰可以看到curFreq
                total+=curFreq;
                //若最高的节点大于2个那么，最高节点的最左一个山峰还能再看一次当前这个节点
                if(st.top().freq>1){
                    total+=curFreq;
                }
            }
         }
    }
    printf("%lld", total);
    return 0;
}