做旅游网站的公司,装饰设计公司官网,html5自学教程,建站工具论坛Every day a Leetcode
题目来源#xff1a;3256. 放三个车的价值之和最大 I
解法1#xff1a;贪心
从大到下排序矩阵所有值, 记为数组v。
转化此题#xff1a;从r*c个数中选取3个数分别给到车1#xff0c;车2#xff0c;和车3#xff0c;使得符合条件的三数之和最大。…Every day a Leetcode
题目来源3256. 放三个车的价值之和最大 I
解法1贪心
从大到下排序矩阵所有值, 记为数组v。
转化此题从r*c个数中选取3个数分别给到车1车2和车3使得符合条件的三数之和最大。 结论可选前2r2c1个最大值作为候选值在此范围枚举求三数之和最大。
代码
/** lc appleetcode.cn id3256 langcpp** [3256] 放三个车的价值之和最大 I*/// lc codestart
class Solution
{
public:long long maximumValueSum(vectorvectorint board){int m board.size(), n m ? board[0].size() : 0;vectortupleint, int, int v;for (int i 0; i m; i)for (int j 0; j n; j)v.push_back({board[i][j], i, j});sort(v.begin(), v.end(), greatertupleint, int, int());long long ans LONG_LONG_MIN;int range min(2 * (m n) 1, (int)v.size());for (int i 0; i range; i){auto [v1, x1, y1] v[i];for (int j i 1; j range; j){auto [v2, x2, y2] v[j];if (x2 x1 || y2 y1)continue;for (int k j 1; k range; k){auto [v3, x3, y3] v[k];if (x3 x1 || y3 y1 || x3 x2 || y3 y2)continue;ans max(ans, (long long)v1 v2 v3);}}}return ans;}
};
// lc codeend结果 复杂度分析
时间复杂度O((mn)3)其中 m 和 n 分别是数组 board 的行数和列数。
空间复杂度O(m * n)其中 m 和 n 分别是数组 board 的行数和列数。
