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

本文主要是介绍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$时同理，所以以哪边大移动哪边的策略一定能计算到最大分数区间。

这篇关于leetcode1793--好子数组的最大分数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---