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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

时间复杂度$O(n)$