5704. 好子数组的最大分数

算法

单调栈 + 双指针 $O(n)$

• 让 i 和 j 均从 k 开始向两边进行扩展，每次计算当前分数，如果大于当前 ans，则更新 ans。
• 如果当前时刻 nums[i-1] > nums[j+1]，显然是让 i 向左边扩展一个下标最优。不然的话，j 向右扩展一个下标，总能让 i 向左边也扩展一步，而保持区间 min 值不变，长度增加，结果增加。反之 nums[i-1] < nums[j+1] 亦然。
• 关键问题在于 nums[i-1] == nums[j+1] 时的处理，这个时候要比较 nums[i-1] 左侧第一个不同于 nums[i-1] 的数和 nums[j+1] 右侧第一个不同于 nums[j+1] 的数。
• 因此，我们需要用单调栈预处理数组 s 和 t。
• s[i] 表示 nums[i] 左侧第一个不同于 nums[i] 的数
• t[i] 表示 nums[i] 右侧第一个不同于 nums[i] 的数

C++ 代码

class Solution {
   public:
    int maximumScore(vector<int>& nums, int k) {
        int n = nums.size();
        int ans = nums[k];
        vector<int> s(n), t(n);
        s[0] = t[n - 1] = -1;
        stack<int> stk;
        stk.push(nums[0]);
        for (int i = 1; i < n; i++) {
            if (stk.size() && stk.top() == nums[i]) {
                stk.pop();
            }
            if (!stk.size())
                s[i] = -1;
            else
                s[i] = stk.top();
            stk.push(nums[i]);
        }
        stack<int> stk2;
        stk.push(nums[n - 1]);
        for (int i = n - 2; i >= 0; i--) {
            if (stk2.size() && stk2.top() == nums[i]) {
                stk2.pop();
            }
            if (!stk2.size())
                t[i] = -1;
            else
                t[i] = stk2.top();
            stk2.push(nums[i]);
        }

        for (int i = k, j = k, m = nums[k]; i >= 0 && j < n;) {
            ans = max(ans, m * (j - i + 1));
            if (i == 0 && j == n - 1) {
                break;
            }
            if (i == 0) {
                m = min(m, nums[++j]);
            } else if (j == n - 1) {
                m = min(m, nums[--i]);
            } else {
                if (nums[i - 1] == nums[j + 1]) {
                    if (s[i - 1] > t[j + 1]) {
                        m = min(m, nums[--i]);
                    } else {
                        m = min(m, nums[++j]);
                    }
                } else if (nums[i - 1] > nums[j + 1]) {
                    m = min(m, nums[--i]);
                } else {
                    m = min(m, nums[++j]);
                }
            }
        }

        return ans;
    }
};

类似题目

1. https://leetcode-cn.com/problems/largest-merge-of-two-strings/
2. 这里相等的时候的处理，和这道题目非常类似

最后试了一下，相等的时候，随便扩展就行，因为我们总会拓展到另一侧，所以不影响

class Solution {
public:
    int maximumScore(vector<int>& nums, int k) {
        int n = nums.size();
        int ans = nums[k];
        for (int i = k, j = k, m = nums[k]; i >= 0 && j < n;) {
            ans = max(ans, m * (j - i + 1));
            if (i == 0 && j == n-1) {
                break;
            }
            if (i == 0) {
                m = min(m, nums[++j]);
            }
            else if (j == n-1) {
                m = min(m, nums[--i]);
            } else {
                 if (nums[i-1] > nums[j+1]) {
                    m = min(m, nums[--i]);
                } else {
                    m = min(m, nums[++j]);
                }
            }
        }

        return ans;
    }
};