题目描述

给你一个整数数组 nums （下标从 0 开始）和一个整数 k 。

一个子数组 (i, j) 的 分数 定义为 min(nums[i], nums[i+1], …, nums[j]) * (j - i + 1) 。一个 好 子数组的两个端点下标需要满足 i <= k <= j 。

请你返回 好 子数组的最大可能 分数 。

(单调栈) $O(n)$

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    int maximumScore(vector<int>& nums, int k) {
        const int N = 100010;
        int left[N], right[N];
        stack<int> s;
        int n = nums.size();
        for(int i = 0; i < n; i++){
            while(!s.empty() && nums[s.top()] >= nums[i]) s.pop();
            if(!s.empty()) left[i] = s.top();
            else left[i] = -1;
            s.push(i);
        }
        while(!s.empty()) s.pop();
        for(int i = n-1; i >= 0; i--){
            while(!s.empty() && nums[s.top()] >= nums[i]) s.pop();
            if(!s.empty()) right[i] = s.top();
            else right[i] = n;
            s.push(i);
        }
        int res = 0;
        for(int i = 0; i < n; i++){
            int l = left[i] + 1, r = right[i] - 1;
            int area = nums[i] * (r - l + 1);
            if(l <= k && r >= k) res = max(res, area); 
        }
        return res;
    }
};