LeetCode 1793. 好子数组的最大分数（单调栈）

示例 1：
输入：nums = [1,4,3,7,4,5], k = 3
输出：15
解释：最优子数组的左右端点下标是 (1, 5) ，
分数为 min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15 。

示例 2：
输入：nums = [5,5,4,5,4,1,1,1], k = 0
输出：20
解释：最优子数组的左右端点下标是 (0, 4) ，
分数为 min(5,5,4,5,4) * (4-0+1) = 4 * 5 = 20 。
 
提示：
1 <= nums.length <= 10^5
1 <= nums[i] <= 2 * 10^4
0 <= k < nums.length

class Solution {
public:
    int maximumScore(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> right(n,-1), left(n,-1);
        stack<int> s;
        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()-1;
            else
                right[i] = n-1;
            s.push(i);
        }
        while(!s.empty()) s.pop();
        for(int i = 0; i < n; i++)
        {
            while(!s.empty() && nums[s.top()] >= nums[i])
                s.pop();
            if(!s.empty())
                left[i] = s.top()+1;
            else
                left[i] = 0;
            s.push(i);
        }
        int maxScore = 0;
        for(int i = 0; i < n; i++)
            if(left[i] <= k && k <= right[i])
                maxScore = max(maxScore, nums[i]*(right[i]-left[i]+1));
        return maxScore;
    }
};