1537. Max Score

Get the Maximum Score

磨练双指针题型的好地方

一切的关键就在题目说的 但凡两个排序好的数组

都享有某个数值时 我们就能把这个数值做 交流道

由此 选择 把访问路径从某数组 切换到 另一个数组

注意 这个选择不是必须齁 只有在换了会更好时 才有理由换道

🗝️🔒两小无猜的针锋相对

两个数组各自准备一根指针🪡

只要两根指针idxOne和idxTwo还没有越过自己所属数组的长度

且他们指向的数值不一致时 我们就不停让对应数值比较小的指针

持续向上递增 直到该指针对位的数值 $\geq$ 另一根指针对位的数值

指针向上递增前 必须先把本来指向的数值 加给自己对应的分数

👩🏻‍❤️‍💋‍👨🏻当情侣达成一致 不再互相拉扯

一旦来到两个指针都指向相同数值的时候

咱们就能进行比较 看看是scoreOne和scoreTwo比较大

把max(scoreOne, scoreTwo) + nums[scoreTwo]加入maxScore

为啥还要把nums[scoreTwo]加上去呢？别忘了

我们是 在递增前那瞬间 才把指针对位的数值放入指针搭配的分数中

等到maxScore吸收完毕后 两根指针自然各自往上递增一格

scoreOne和scoreTwo因此清零重新开始

总会有人需要多留下来善后

好比Merge Sort的Merge阶段 肯定会有某个数组先被访问完

另一个数组还有数值没被访问完 我们这题也是一样的情形

必然有其中一个数组的指针 尚未扫过该数组全部的数值

因此得让该指针持续递增 将数值加进自己负责的分数

最后scoreOne和scoreTwo再取较大者 加到maxScore

然后答案便搞定啰 当然这题有个题目的老细节

就是由于数值叠加过程可能会超大 引起天文数字

因此需要$10^9 + 7$作为Modulo 控制maxScore大小再回传

整道算法就是两根指针变量 三种分数变量 一个Modulo常量

合计六个变数需要开 因此空间复杂度$O(1)$

时间复杂度非常显眼就是$O(\text{|nums1|} + \text{|nums2|})$ 因为每个数值只会被扫描一遍

C++

#include <cmath>
#include <vector>
using namespace std;

int findMaxScore(vector<int>& nums1, vector<int>& nums2) { // LeetCode Q.1537.
    long long maxScore = 0; // Must use long long to prevent overflow.
    long long scoreOne = 0, scoreTwo = 0;

    int modulo = pow(10, 9) + 7;

    int idxOne = 0, idxTwo = 0;

    while (idxOne < nums1.size() && idxTwo < nums2.size()) {
        while (idxOne < nums1.size() && nums1[idxOne] < nums2[idxTwo]) {
            scoreOne += nums1[idxOne];
            idxOne++;
        }
        if (idxOne == nums1.size()) break; // Array 1 can't catch up.

        while (idxTwo < nums2.size() && nums2[idxTwo] < nums1[idxOne]) {
            scoreTwo += nums2[idxTwo];
            idxTwo++;
        }
        if (idxTwo == nums2.size()) break; // Array 2 can't catch up.

        if (nums1[idxOne] == nums2[idxTwo]) { // Arrays can now compare scores.
            scoreOne += nums1[idxOne];
            scoreTwo += nums2[idxTwo];

            maxScore += max(scoreOne, scoreTwo);
            if (maxScore > modulo) maxScore %= modulo; // Control size.

            scoreOne = 0, scoreTwo = 0; // Reset for next while iteration.
            idxOne++;
            idxTwo++;
        }
    }

    while (idxOne < nums1.size()) { // Remaining nums from array 1.
        scoreOne += nums1[idxOne];
        idxOne++;
    }

    while (idxTwo < nums2.size()) { // Remaining nums from array 2.
        scoreTwo += nums2[idxTwo];
        idxTwo++;
    }

    maxScore += max(scoreOne, scoreTwo);
    return maxScore % modulo; // Control size.
}

Python

def find_max_score(nums_1: list[int], nums_2: list[int]) -> int:  # LeetCode Q.1537.
    max_score = 0
    modulo = 10 ** 9 + 7

    score_1, score_2 = 0, 0

    idx_1, idx_2 = 0, 0

    while idx_1 < len(nums_1) and idx_2 < len(nums_2):
        while idx_1 < len(nums_1) and nums_1[idx_1] < nums_2[idx_2]:
            score_1 += nums_1[idx_1]
            idx_1 += 1
        
        if idx_1 == len(nums_1): break  # Array 1 can't catch up.

        while idx_2 < len(nums_2) and nums_2[idx_2] < nums_1[idx_1]:
            score_2 += nums_2[idx_2]
            idx_2 += 1
        
        if idx_2 == len(nums_2): break  # Array 2 can't catch up.

        if nums_1[idx_1] == nums_2[idx_2]:  # Arrays can now compare scores.
            score_1 += nums_1[idx_1]
            score_2 += nums_2[idx_2]

            max_score += max(score_1, score_2)
            if max_score > modulo: max_score %= modulo  # Control size.
            
            score_1, score_2 = 0, 0  # Reset for next while iteration.
            idx_1 += 1
            idx_2 += 1

    while idx_1 < len(nums_1):  # Remaining nums from array 1.
        score_1 += nums_1[idx_1]
        idx_1 += 1

    while idx_2 < len(nums_2):  # Remaining nums from array 2.
        score_2 += nums_2[idx_2]
        idx_2 += 1

    max_score += max(score_1, score_2)
    return max_score % modulo  # Control size.