Leetcode1793. Maximum Score of a Good Subarray

给定一个数组和一个下标$k$

子数组$(i,j)$分数定义为$\min \left(nums[i],nums[i+1],\cdots ,nums[j]\right)\ast \left(j-i+1\right)$
其中$i\le k\le j$

找到最大的子数组分数

其实这题有点像是接雨水那个题目

从$k$出发，哪一边大就往哪一边扩展

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

时间复杂度$O(n)$