题目

题目链接🔗
给你一个整数数组 $nums$ （下标从 $0$ 开始）和一个整数 $k$ 。

一个子数组 $(i,j)$ 的 分数 定义为 $min(nums[i],nums[i+1],...,nums[j])\ast (j-i+1)$。一个 好 子数组的两个端点下标需要满足 $i\le k\le j$ 。

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

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

示例 2：
输入：nums = [5,5,4,5,4,1,1,1], k = 0
输出：20
解释：最优子数组的左右端点下标是 (0, 4) ，分数为 $min(5,5,4,5,4)\ast (4-0+1)=4\ast 5=20$ 。

提示：

• $1\le nums.length\le 10^5$
• $1\le nums[i]\le 2\ast 10^4$
• $0\le k<nums.length$

思路

为了解决这个问题，我们可以使用单调栈进行预处理。我们可以维护两个数组 $left$ 和 $right$，其中 $left[i]$ 和 $right[i]$ 分别表示 $nums[i]$ 的左边和右边比 $nums[i]$ 小，且离 $nums[i]$ 最近的位置。因此，以 $nums[i]$ 为最小值的最长子数组就应该是 $(left[i],right[i])$。当 $k$ 在 $(left[i],right[i])$ 范围内时，我们维护 $nums[i]\times (right[i]-left[i]-1)$ 的最大值即可。

代码

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

复杂度分析

时间复杂度

• 预处理阶段的时间复杂度为 O(n)，其中 n 是数组的长度。
• 寻找最大分数时，遍历了数组，时间复杂度为 O(n)。

综上所述，总的时间复杂度为 O(n)。

空间复杂度

• 使用了额外的数组 left 和 right，它们的空间复杂度均为 O(n)。
• 使用了一个栈，最坏情况下需要存储整个数组，因此空间复杂度为 O(n)。

综上所述，总的空间复杂度为 O(n)。

结果

总结

通过单调栈预处理出 $left$ 和 $right$ 数组，可以在 $O(n)$ 的时间复杂度内解决这个问题。这种方法利用了单调栈的性质，使得寻找以 $nums[i]$ 为最小值的子数组的左右边界成为可能。