美团笔试算法题第二题（3.22）

题目描述：给定一个 n 个数，求解有多少个长度为奇数的区间的中位数位置刚好就在正中间。

输入：

第一行输入 t ，表示 t 组输入

第二行输入 n，数组大小为 n

第三行输入 n 个数。

t 组输入的 n 的个数和不超过 10000。

思路：通过数据，可以预估该题时间复杂度，初步预估O（nlogn），不过发现二分啥的都解不了。思考O（n * n）思路。发现常数不大，完全没问题。

思路一：（dp数数）

数数题，一般思路，遍历一遍数组，在 i 位置时统计添加一个 a[i] 元素，会新增多少个满足答案的区间。

例：3 2 1 4 5

i = 1时，新增 1 个区间。[1, 1]

i = 2时，新增 1 个区间。[2, 2]

i = 3时，新增 2 个区间。[1, 3], [3, 3]

i = 4时，新增 1 个区间。[4, 4]

i = 5 时，不就新增了 2 个区间满足条件。[3, 5]，[5, 5]

再思考，如何一次统计出前面所有满足条件的区间呢。

例：1 2 3 4 5 6 7

i = 7时，不就有四个区间可能会提升答案。[7, 7], [5, 7], [3, 7], [1, 7]。

那么可以将题目转化为，统计这些区间中有多少个中位数是在中间。

所以我们可以遍历这些区间的中间的数，判断是不是对应区间的中位数即可。

再思考，那么该如何判断 区间中任意一个数 x 是一个区间的中位数呢？

大于 x 的数的个数 = 小于 x 的数的个数 《=》 x 是这个区间的中位数

那么只需要遍历一遍这个区间，大于 x，则sum ++。小于 x ，则sum --。若sum = 0，表示x就是这个区间的中位数。

所以我们一个数组去动态的预处理 这些区间中间的数的权值，然后遍历一遍判断 是否等于 0, 若等于 0，则ans ++。

例：3 4 2 1 5 6 7

i = 7时，可能提升答案的四个区间为：[1, 7], [3, 7], [5, 7], [7, 7]。

对于[1, 7]区间：中间的位置为4，值为 1 ，其他数都比 1 大，所以 sum[4] = 6；

对于[3, 7]区间：中间的位置为5，值为5，2和1比5小，6和7比5大，所以sum[5] = 0；

对于[5, 7]区间：中间的位置为6，值为6，同理sum[6] = 0；

对于[7, 7]区间：中间的位置为7，值为7，同理sum[7] = 0；

所以预处理后的这个数组值为：

0 0 0 6 0 0 0

其中有三个中间位置的权值为 0 ，估 ans += 3。

那么该如何动态进行维护这个权值数组呢，可以自行思考下，实现思路在代码里有解释。

含有注释代码：

#include <bits/stdc++.h>
using namespace std;

void solve(){
    int n;
    cin >> n;
    vector<int>a(n + 1, 0);

    for(int i = 1; i <= n; i ++){
        cin >> a[i];
    }
    int ans = n; // 提前预处理出长度为 1 的区间
    vector<int>sum(n + 1, 0);
    for(int i = 1; i <= n; i ++){ // 按照上面思路，每次统计新增一个a[i]元素，ans会增加多少。
        
        for(int j = 1; j <= (i - 1) / 2; j ++){ // 遍历 i位置 前面可能提升答案的区间的中间的数，i - j 就为一个区间的中间数
            // 判断新增的a[i], 对这些中间数权值的改变
            if(a[i - j] < a[i]){
                sum[i - j] ++;
            }else if(a[i - j] > a[i]){
                sum[i - j] --;
            }
            
            // 要是这个中间数的权值 == 0，则ans ++
            if(sum[i - j] == 0){
                ans ++;
            }
        }
        
        // 区间[1, (i + 1) / 2] 的值 对 区间[i / 2, i - 1] 权值的更新。
        // 例：1, 2, 3, 4, 5, 6, 7 当 i = 6, 就需要预处理[1, 3]区间对[4, 6]区间权值的更新。
        // 例：1, 2, 3, 4, 5, 6    当 i = 5, 就需要预处理[2, 3]区间对[4, 5]区间权值的更新。
        //                                   而位置1 对 位置 3的更新并不影响后续结果，因为后续将不会使用到这个中间数。

        // 前面数对后面中间数的权值更新，通过每次更新一部分使得成立。
        // 可自行模拟这个过程理解。上面例子只是直观的感受更新区间的相对位置，建议从小的模拟。
        for(int j = 1; j <= (i + 1) / 2; j ++){
            int k = i / 2;
            if(a[j] < a[j + k]){
                sum[j + k] --;
            } else if(a[j] > a[j + k]){
                sum[j + k] ++;
            }
        }
    }

    cout << ans << endl;
}

int main() {
    int t;
    cin >> t;
    while(t --) solve();
}

无注释代码：

#include <bits/stdc++.h>
using namespace std;

void solve(){
    int n;
    cin >> n;
    vector<int>a(n + 1, 0);

    for(int i = 1; i <= n; i ++){
        cin >> a[i];
    }
    int ans = n; 
    vector<int>sum(n + 1, 0);
    for(int i = 1; i <= n; i ++){
        
        for(int j = 1; j <= (i - 1) / 2; j ++){ 
            if(a[i - j] < a[i]){
                sum[i - j] ++;
            }else if(a[i - j] > a[i]){
                sum[i - j] --;
            }

            if(sum[i - j] == 0){
                ans ++;
            }
        }
        
        for(int j = 1; j <= (i + 1) / 2; j ++){
            int k = i / 2;
            if(a[j] < a[j + k]){
                sum[j + k] --;
            } else if(a[j] > a[j + k]){
                sum[j + k] ++;
            }
        }
    }

    cout << ans << endl;
}

int main() {
    int t;
    cin >> t;
    while(t --) solve();
}

思路二：（中心扩展）

#include <bits/stdc++.h>
using namespace std;

int suan(int x, int y){
    if(x > y) return 1;
    else return -1;
}

void solve(){
    int n;
    cin >> n;
    vector<int>a(n + 1, 0);

    for(int i = 1; i <= n; i ++){
        cin >> a[i];
    }
    int ans = n; // 提前预处理出长度为 1 的区间
    for(int i = 1; i <= n; i ++){
        int sum = 0;
        for(int j = 1; i - j >= 1 && i + j <= n; j ++){
            int l = i - j, r = i + j;
            sum += suan(a[i], a[l]) + suan(a[i], a[r]);
            if(sum == 0){
                ans ++;
            }
        }
    }

    cout << ans << endl;
}

int main() {
    int t;
    cin >> t;
    while(t --) solve();
}