保卫方案（京东笔试题）

Question展开目录

战争游戏的至关重要环节就要到来了，这次的结果将决定王国的生死存亡，小 B 负责首都的防卫工作。首都位于一个四面环山的盆地中，周围的 n 个小山构成一个环，作为预警措施，小 B 计划在每个小山上设置一个观察哨，日夜不停的瞭望周围发生的情况。一旦发生外地入侵事件，山顶上的岗哨将点燃烽烟，若两个岗哨所在的山峰之间没有更高的山峰遮挡且两者之间有相连通路，则岗哨可以观察到另一个山峰上的烽烟是否点燃。由于小山处于环上，任意两个小山之间存在两个不同的连接通路。满足上述不遮挡的条件下，一座山峰上岗哨点燃的烽烟至少可以通过一条通路被另一端观察到。对于任意相邻的岗哨，一端的岗哨一定可以发现一端点燃的烽烟。小 B 设计的这种保卫方案的一个重要特性是能够观测到对方烽烟的岗哨对的数量，她希望你能够帮她解决这个问题。

输入描述展开目录

输入中有多组测试数据，每一组测试数据的第一行为一个整数 n (3≤n≤10^6^), 为首都周围的小山数量，第二行为 n 个整数，依次表示为小山的高度 h（1≤h≤10^9^）.

输出描述展开目录

对每组测试数据，在单独的一行中输出能相互观察到的岗哨的对数。

思路展开目录

你要说这是单调栈板子题似乎有点看不起京东。总结一下，两座山 A,B 之间能通信的要求是，A,B 之间的点都比这个点小，确实看到这很容易想到单调栈，构建一个单调递减栈，以 1,2,4,5,3 为例。

首先找到这些元素中的最大值，以最大值作为起点进行入栈操作，那么 5,3,1 依次入栈，接下来要入栈的是 2，2 大于 1，所以 1 出栈，1 的左边 (3)，右边 (2)。那么 1 是可以看到 2 和 3 的，有两对。res += 2

4 准备进栈，4 大于 2，所以 2 要出栈，2 的左边 (3)，右边 (4)，res += 2。

同理，3 也要出栈，res += 2。此时栈里面只有 4 和 5 作为一对，res += 1。

上述是一种特殊情况，没有重复元素时，如果有重复元素，假设数组是 4,4,5,5,6,6，此时 stack 中存的是一个 pair，pair 中包含两个变量，当前存的值，以及该值的个数，比方说遍历数组，首先是下标为 4 的 6 先进栈，然后下标为 5 的 6 进栈，因为值相同，所以 pair.times++，然后两个 4 进栈，此时的情况见下图
4 要出栈，但是此时 res 要加多少呢？这其实是一个排列组合的问题 res += C (4,2)+2*2，然后两个 5 都进来了，数组遍历结束，但是此时栈中还有值
数组遍历完了，但是栈中还有值，这种情况要特殊讨论

栈中元素个数大于 2，res += C (stack.peek ().times,2) + 2*stack.pop ().times
栈中元素个数等于 2
- 如果栈底元素的 times==1，则 res += C (stack.peek ().times,2)+stack.pop ().times
- 如果栈底元素的 times !=1 ，则 res += C (stack.peek ().times,2)+2*stack.pop ().times
栈中元素小于 2（就一个），res += C (stack.pop ().times,2)

代码展开目录

package nowcoder;
import java.util.*;
public class Main {
    public static int nexIndex(int size,int i) {
        return i < (size - 1) ? (i + 1) : 0;
    }
    private static class Pair {
        public int value;
        public int times;
        Pair(int value) {
            this.value = value;
            this.times = 1;
        }
    }
    public static long getInternalSum(int k) {
        return k == 1L ? 0L : (long)k * (long)(k - 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++)
            maxIndex = arr[maxIndex] < arr[i] ? i : maxIndex;
        int value = arr[maxIndex];//最大值
        int index = nexIndex(size,maxIndex);//最大值的下一个
        long res = 0L;
        Stack<Pair> stack = new Stack<Pair>();
        stack.push(new Pair(value));
        while(index != maxIndex) {
            value = arr[index];
            while(!stack.isEmpty() && stack.peek().value < value) {
                int times = stack.pop().times;
                res += getInternalSum(times) + 2 * times;//C(times，2) + 2 * times
            }
            if(!stack.isEmpty() && stack.peek().value == value) 
                stack.peek().times++;
            else 
                stack.push(new Pair(value));
            index = nexIndex(size,index);
        }
        while(!stack.isEmpty()) {
            int times = stack.pop().times;
            res += getInternalSum(times);
            if(!stack.isEmpty()) {
                res += times;
                if(stack.size() > 1)
                    res += times;
                else 
                    res += stack.peek().times > 1 ? times : 0;
            }
        }
        return res;
    }
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while(cin.hasNext()) {
            int n = cin.nextInt();
            int[] arr = new int[n];
            HashSet<Integer> tmp = new HashSet<Integer>();
            for(int i = 0;i < n;i++) {
                arr[i] = cin.nextInt();
                tmp.add(arr[i]);
            }
            if(tmp.size() == n)//没有重复元素，直接用结论
                System.out.println((long)2 * n - 3);
            else
                System.out.println(communications(arr));
        }
    }
}

Catalog