【Leetcode】274. H-Index（水平面上的最大正方形）

野性酷女 2022-01-15 02:49 155阅读 0赞

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.

According to the [definition of h-index on Wikipedia][]: "A scientist has index *h* if *h* of his/her *N* papers have **at least** *h* citations each, and the other *N − h* papers have **no more than** *h* citations each."

**Example:**

Input: citations = [3,0,6,1,5]
    Output: 3 
    Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively.              Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, her h-index is 3.

**Note:** If there are several possible values for *h*, the maximum one is taken as the h-index.

题目大意：

给出无序的文献的影响因子，我们需要找出一个H值。

H值：影响因子不大于当前影响因子的著作数，反之亦然。呈现在图上就是找出将数组从小到大排序之后能够形成的最大正方形的边长。

class Solution {
    private:
        int helper(vector<int>& heights) {
            int n = heights.size();
            vector<int> l(n,0),r(n,n);
            for(int i = 1;i<n;i++){
                int p = i-1;
                while(p>=0&&heights[p]>=heights[i]){     
                    p = l[p] - 1;
                }
                l[i] = p + 1;
            }
            for(int i = n-2;i>=0;i--){
                int p = i+1;
                while(p<n&&heights[p]>=heights[i]){
                    p=r[p];
                }
                r[i] = p;
            }
            int ans = 0;
            for(int i = 0;i<n;i++){
                ans = max(ans, min((r[i]-l[i]),heights[i])*min((r[i]-l[i]),heights[i]));
            }
            
            return sqrt(ans);
        }
    public:
        int hIndex(vector<int>& citations) {
            sort(citations.begin(), citations.end());
            return helper(citations);
        }
    };

[definition of h-index on Wikipedia]: https://en.wikipedia.org/wiki/H-index