leetcode 1014 最佳觀光組合（枚舉右維護左）

2024年9月22日#leetcode32

AI 翻譯

這篇文章透過AI由簡體中文翻譯成繁體中文。查看原文

AI 生成的摘要

原題目來自 LeetCode，要求找出最佳觀光配對的分數。最初的解法使用雙重循環，時間複雜度為 $$O(n^2)$$，無法通過所有測試點。為了降低複雜度，將目標函數轉化為 (value[i] + i) + (value[j] - j)，然後遍歷右下標 $$j$$，維護左側的最大值 $$value[i] + i$$。最終的優化解法時間複雜度為 $$O(n)$$，如下所示： ```cpp class Solution { public: int maxScoreSightseeingPair(vector<int>& values) { int ans = 0; int mx = 0; for(int j = 0; j < values.size(); ++j){ ans = max(ans, mx + values[j] - j); mx = max(mx, values[j] + j); } return ans; } }; ``` 這種方法可以有效解決類似的雙變量問題。

原題#

https://leetcode.cn/problems/best-sightseeing-pair/description/

思路#

雙循環枚舉

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int max = 0;
        int length = values.size();
        for(int i = 0; i < length; ++i)
            for(int j = i + 1; j < length; ++j)
                if(values[i] + values[j] + i - j > max)
                    max = values[i] + values[j] + i - j;
        return max;
    }
};

但不能通過全部測試點。時間複雜度過高 $O(n^2)$

題解#

思路：降低複雜度。想辦法弄成 $O(n)$ 的複雜度就好了。

目標函數移項得到 (value[i] + i) + (value[j] - j) ，然後將 value[i] + i 當做整體，將 value[j] - j 當做整體。就轉化為了兩數的最大值。

考慮遍歷 j 然後維護 value[i] + i 的最大值，所以代碼可以變為

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int ans = 0;
        int mx = 0;
        for(int j = 0; j < values.size(); ++j){
            ans = max(ans, mx + values[j] - j); 
            mx = max(mx, values[j] + j);
        }
        return ans;
    }
};

枚舉右維護左#

對於類似 leetcode 1014 所示的雙變量問題，可以選擇枚舉右下標 $j$ ，來轉化為單變量問題求解。

類似題目參看 https://leetcode.cn/circle/discuss/mOr1u6/