leetcode1793--好子数组的最大分数

1. 题意

给定一个数组，求包含$a[k]$的$min(arr)\times arr.size(),s.t.a[k]\in arr$
好子数组的最大分数

与柱形图面积相似，只是区间需要包含$a[k]$。

2. 题解

2.1 单调栈

求出左边第一个小和右边第一个小形成的区间包含$a[k]$即可。

比原来代码多了一个判断。

class Solution {
public:
    int maximumScore(vector<int>& nums, int k) {
        
        int n = nums.size();

        stack<int> p;
        vector<int> left(n, -1);
        vector<int> right(n, n);

        for (int i = 0;i < n; ++i) {
            while (!p.empty() && nums[i] <= nums[p.top()])
                p.pop();
            if (!p.empty())
                left[i] = p.top();
            p.push(i);
        }

        p = stack<int>();

        for (int i = n - 1; ~i; --i) {
            while (!p.empty() && nums[i] <= nums[p.top()]) 
                p.pop();
            if (!p.empty())
                right[i] = p.top();
            p.push(i);
        }

        int ans = 0;
        for (int i = 0;i < n; ++i) {

            if (left[i] < k && right[i] > k) {
                ans = max(ans, (right[i] - left[i] - 1) * nums[i]);
            }
        }


        return ans;
    }
};

2.2 双指针

我们从$k$出发，那边的数比较大，我们就自增哪边；然后算此时区间的分数。

• 自己代码

class Solution {
public:
    int maximumScore(vector<int>& nums, int k) {
        int n = nums.size();
        int left = k - 1, right = k + 1;
        int ans = nums[k];
        int minv = nums[k];
        while(left > -1 || right < n) {
            if (left > -1 && right < n) {
                if (nums[left] <= nums[right]){
                    minv = min(minv, nums[right]);
                    ++right;
                }
                else {
                    minv = min(minv, nums[left]);
                    --left;
                }
            }
            else if ( left > -1) {
                minv = min(minv, nums[left]);
                --left;
            }
            else {
                minv = min(minv, nums[right]);
                ++right;
            }
            ans = max(ans, (right - left - 1) * minv);
        }

        return ans;
    }
};

• 灵神代码
  直接循环$n-1$次

class Solution {
public:
    int maximumScore(vector<int> &nums, int k) {
        int n = nums.size();
        int ans = nums[k], min_h = nums[k];
        int i = k, j = k;
        for (int t = 0; t < n - 1; t++) { // 循环 n-1 次
            if (j == n - 1 || i && nums[i - 1] > nums[j + 1]) {
                min_h = min(min_h, nums[--i]);
            } else {
                min_h = min(min_h, nums[++j]);
            }
            ans = max(ans, min_h * (j - i + 1));
        }
        return ans;
    }
};

// 作者：灵茶山艾府

主要是证明正确性：

假设最大分数值的区间为$[L,R]$;

我们只需要证明当左指针$lp$在$L$时，右指针$rp$一直移动到$R$。

和右指针$rp$在$R$时，左指针$lp$一直移动到$R$。

假设$min(a[i])=m,i\in [L,R]$;

当$lp=L$时，$a[lp-1]<m$一定成立；否则最大分数区间可以将该值包进来。

此时$a[rp]\ge m>a[lp]$，所以此时一定是$rp$指针一直移动到$R$。

当$rp=R$时同理，所以以哪边大移动哪边的策略一定能计算到最大分数区间。