Leetcode 第 365 场周赛题解

Leetcode 第 365 场周赛题解

题目1：2873. 有序三元组中的最大值 I

思路

暴力。

代码

/** @lc app=leetcode.cn id=2873 lang=cpp** [2873] 有序三元组中的最大值 I*/// @lc code=start
class Solution
{
public:long long maximumTripletValue(vector<int> &nums){int n = nums.size();long long ans = INT_MIN;for (int i = 0; i < n - 2; i++)for (int j = i + 1; j < n - 1; j++)for (int k = j + 1; k < n; k++)ans = max(ans, (long long)(nums[i] - nums[j]) * nums[k]);return ans >= 0 ? ans : 0;}
};
// @lc code=end

复杂度分析

时间复杂度：O(n³)，其中 n 是数组 nums 的长度。

空间复杂度：O(1)。

题目2：2874. 有序三元组中的最大值 II

思路

枚举 k，我们需要知道 k 左边 nums[i]−nums[j] 的最大值。

使用 pre_max 维护 k 之前的 nums[i] 的最大值，使用 max_diff 维护 nums[i]−nums[j] 的最大值。

每次遍历一个 nums[i]，都更新 ans，pre_max，max_diff：

1. ans = max(ans, (long long)max_diff * nums[i])
2. max_diff = max(max_diff, pre_max - nums[i])
3. pre_max = max(pre_max, nums[i])

最后 return ans >= 0 ? ans : 0 即为答案。

代码

/** @lc app=leetcode.cn id=2874 lang=cpp** [2874] 有序三元组中的最大值 II*/// @lc code=start
class Solution
{
public:long long maximumTripletValue(vector<int> &nums){int n = nums.size();long long ans = INT_MIN;int max_diff = 0, pre_max = 0;for (int i = 0; i < n; i++){ans = max(ans, (long long)max_diff * nums[i]);max_diff = max(max_diff, pre_max - nums[i]);pre_max = max(pre_max, nums[i]);}return ans >= 0 ? ans : 0;}
};
// @lc code=end

复杂度分析

时间复杂度：O(n)，其中 n 是数组 nums 的长度。

空间复杂度：O(1)。

思路2

枚举 j

pre_max 数组维护 nums[i] 的最大值。

max_suffix 数组维护 nums[k] 的最大值。

更新 ans = max(ans, (long long)(pre_max[j - 1] - nums[j]) * max_suffix[j + 1])。

最后 return ans >= 0 ? ans : 0 即为答案。

class Solution
{
public:long long maximumTripletValue(vector<int> &nums){int n = nums.size();long long ans = INT_MIN;vector<int> pre_max(n, 0);pre_max[0] = nums[0];for (int i = 1; i < n; i++)pre_max[i] = max(pre_max[i - 1], nums[i]);vector<int> max_suffix(n, 0);max_suffix[n - 1] = nums[n - 1];for (int i = n - 2; i >= 0; i--)max_suffix[i] = max(max_suffix[i + 1], nums[i]);for (int j = 1; j < n - 1; j++)ans = max(ans, (long long)(pre_max[j - 1] - nums[j]) * max_suffix[j + 1]);return ans >= 0 ? ans : 0;}
};

题目3：2875. 无限数组的最短子数组

思路

滑动窗口。

设数组 nums 的总和为 total，长度为 n。

已知数组 infinite_nums 是通过无限地将 nums 的元素追加到自己之后生成的。

假设有下面这种情况：

去掉中间一整段完整的 nums 数组，新的目标值为 target % total。

问题转化为在 nums + nums[1,…,n-1] 这个长度为 2 * n - 1 的数组上，求满足元素和 等于 target % total 的最短子数组，设这个长度为 len。

加上 target / total 个完整数组的长度，最终的长度为 len + target / total * n。

代码

/** @lc app=leetcode.cn id=2875 lang=cpp** [2875] 无限数组的最短子数组*/// @lc code=start// 滑动窗口class Solution
{
public:int minSizeSubarray(vector<int> &nums, int target){int n = nums.size();long long total = accumulate(nums.begin(), nums.end(), 0LL);for (int i = 0; i < n - 1; i++)nums.push_back(nums[i]);long long sum = 0;int left = 0, len = INT_MAX;for (int right = 0; right < 2 * n - 1; right++){sum += nums[right];while (sum > target % total){sum -= nums[left];left++;}int cur_len = right - left + 1;if (sum == target % total)len = min(len, cur_len);}return len == INT_MAX ? -1 : len + target / total * n;}
};
// @lc code=end

复杂度分析

时间复杂度：O(n)，其中 n 为 nums 数组的长度。

空间复杂度：O(n)，延长了 nums 数组。

题目4：2876. 有向图访问计数

超出能力范围。

题解：【模板】内向基环树