美团笔试--小美的众数

比较有意思的题目，看了看别人的思路发现和我不太一样，记录一下

小美拿到一个数组。她希望你求出所有区间众数之和。

定义区间的众数为出现次数最多的那个数。如果有多个数出现次数最多，那么众数是其中最小的那个数。

n表示数组大小，200000范围

ai 取值为1或者2

输出一个正整数，代表所有区间的众数之和

示例

输入

3

2 1 2

输出

9

思路：

维护一个2*n+1的区间

这个区间的表示如下

我们只需要处理新增加的元素对应的新区间即可

比如处理第i个元素的时候，只需要关注[0,i],[1,i],[2,i].......[i,i]这些新增加的区间即可

因为知道这些新增加的区间其实就是上一个元素i-1对应的所有新区间后面添加一个元素a[i],以及添加一个由a[i]单独组成的区间

所以，我们可以从上一个新增区间的状态获取当前区间的状态，

即，当新元素为1的时候，就相当于1与2数量相同的区间数量对应的index向右边移动一次，为2时向左移动，并且添加对应的单独元素组成的区间，也就是在对应的元素+1

最后维护好1比2多的总区间数量以及2比1多的总区间数量即可

复杂度O(n)

public class s4 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        // 记录数组，0~n-1部分从n-1下标开始记录1比2的数量多1，2，3，4.....个的区间数量
        // 同理n+1~2n+1部分表示2比1多1，2，3，4....的区间数量
        int[] vis = new int[ 2 * n + 1];
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        long res = 0L;
        // 1与2数量相同的位置index
        int pos = n;
        // 1比2数量多的区间数量总和
        int sum1 = 0;
        // 2比1数量多的区间数量总和
        int sum2 = 0;
        // 每次只处理新增加的区间
        for (int i = 0; i < n; i++) {
            if (a[i] == 1){
                // 新增加一个空的区间
                vis[pos]++;
                // 当前位置是1，所有区间都会加上一个1，所以。pos向左边移动一下
                // 移动的时候维护好sum1和sum2
                sum1 += vis[pos];
                pos++;
                sum2 -= vis[pos];
            }else{
                vis[pos]++;
                sum2 += vis[pos];
                pos--;
                sum1 -= vis[pos];
            }
            // sum2全是众数为2的区间数量，sum1全是众数为1的数量
            res += (sum2*2);
            res += sum1;
            // 1和2数量相同，认定1为众数
            res += vis[pos];
        }
        System.out.println(res);
    }
}