Sunforger

Sunforger

leetcode 1014 最適な観光コンビネーション(右を列挙して左を維持)

原題#

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(n2)O(n^2)

题解#

思路:降低复杂度。想办法弄成O(n)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 所示的双变量问题,可以选择枚举右下标 jj,来转化为单变量问题求解。

类似题目参看 https://leetcode.cn/circle/discuss/mOr1u6/

読み込み中...
文章は、創作者によって署名され、ブロックチェーンに安全に保存されています。