题目描述

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

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

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

样例

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

输入：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

算法

(单调栈) $O(n)$

1. 对于每个位置 $i$，求出最大的 $l_i < i$ 满足 $a(l_i) \le a(i)$，如果不存在则 $l_i = -1$。
2. 同理，对于每个位置 $i$，求出最小的 $r_i > i$ 满足 $a(r_i) < a(i)$，如果不存在则 $r_i = n$。
3. 此时，枚举每个位置 $i$，如果 $l_i < k$ 并且 $r_i > k$，则区间 $[l_i + 1, r_i - 1]$ 是以 $a(i)$ 为最小值的极大区间，更新答案。
   • 注意，这里 $l_i$ 是左侧第一个 不大于 $a(i)$ 的位置，但 $r_i$ 一定是右侧第一个 严格小于 $a(i)$ 的位置。尽管这样，仍然可以保证求出正确答案。
   • 对于其他问题，如果两侧都需要严格或者非严格，则需要做两次单调栈。
4. $l_i$ 和 $r_i$ 可以通过一次单调栈快速求解，参考最大子矩阵的解法：维护一个 非严格单调递增 的栈。
   • 如果是严格单调递增的栈，则变为了 $l_i$ 是左侧第一个 严格小于 $a(i)$ 的位置，$r_i$ 是右侧第一个 不大于 $a(i)$ 的位置。
5. 如果当前元素小于栈顶元素，则栈顶元素出栈。出栈时，栈顶元素的 $r_i$ 就是当有位置，栈顶元素的 $l_i$ 就是出栈后新的栈顶。以此类推，直到当前元素的下标可以进栈。
6. 最后留在栈中的元素需要依次弹出，并赋值 $l_i$。

时间复杂度

• 每个元素进栈一次，出栈一次，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储单调栈。

C++ 代码

class Solution {
public:
    int maximumScore(vector<int>& nums, int k) {
        const int n = nums.size();
        vector<int> l(n, -1), r(n, n);

        stack<int> st;
        for (int i = 0; i < n; i++) {
            while (!st.empty() && nums[i] < nums[st.top()]) {
                int top = st.top();
                st.pop();
                if (!st.empty()) l[top] = st.top();
                r[top] = i;
            }
            st.push(i);
        }
        while (!st.empty()) {
            int top = st.top();
            st.pop();
            if (!st.empty()) l[top] = st.top();
        }

        int ans = 0;
        for (int i = 0; i < n; i++)
            if (l[i] < k && r[i] > k)
                ans = max(ans, nums[i] * (r[i] - l[i] - 1));

        return ans;
    }
};