Leetcode 第 139 场双周赛题解

Leetcode 第 139 场双周赛题解

题目1：3285. 找到稳定山的下标

思路

遍历。

代码

class Solution
{
public:vector<int> stableMountains(vector<int> &height, int threshold){vector<int> ans;for (int i = 1; i < height.size(); i++)if (height[i - 1] > threshold)ans.push_back(i);return ans;}
};

复杂度分析

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

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

题目2：3286. 穿越网格图的安全路径

思路

广度优先搜索。

代码

#
# @lc app=leetcode.cn id=3286 lang=python3
#
# [3286] 穿越网格图的安全路径
## @lc code=start
class Solution:def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:m, n = len(grid), len(grid[0])vis = [[False] * n for _ in range(m)]vis[0][0] = Truedx = [0, 1, 0, -1]dy = [1, 0, -1, 0]@cachedef dfs(x: int, y: int, h: int) -> bool:if h <= 0:return Falseif x == m - 1 and y == n - 1 and h > 0:return Truefor i in range(4):nx = x + dx[i]ny = y + dy[i]if nx >= 0 and nx < m and ny >= 0 and ny < n and vis[nx][ny] == False:vis[nx][ny] = Trueif dfs(nx, ny, h - grid[nx][ny]):return Truevis[nx][ny] = Falsereturn Falsereturn dfs(0, 0, health - grid[0][0])
# @lc code=end

复杂度分析

时间复杂度：O(m * n)，其中 m 和 n 分别为 grid 的行数和列数。

空间复杂度：O(m * n)，其中 m 和 n 分别为 grid 的行数和列数。

题目3：3287. 求出数组中最大序列值

思路

前后缀分解。

把数组nums 分成左右两部分，左部和右部分别计算所有长为 k 的子序列的 OR 都有哪些值。

两两组合计算 XOR，取其中最大值作为答案。

代码

/** @lc app=leetcode.cn id=3287 lang=cpp** [3287] 求出数组中最大序列值*/// @lc code=start
class Solution
{
private:static const int MX = 1 << 7;public:int maxValue(vector<int> &nums, int k){int n = nums.size();vector<array<bool, MX>> pre(k + 1);vector<array<bool, MX>> suf(n - k + 1);vector<array<bool, MX>> dp(k + 1);dp[0][0] = true;// 状态转移for (int i = n - 1; i >= k; i--){int v = nums[i];for (int j = min(k - 1, n - 1 - i); j >= 0; j--){for (int x = 0; x < MX; x++)if (dp[j][x])dp[j + 1][x | v] = true;}if (i <= n - k)suf[i] = dp[k];}int ans = 0;pre[0][0] = true;for (int i = 0; i < n - k; i++){int v = nums[i];for (int j = min(k - 1, i); j >= 0; j--)for (int x = 0; x < MX; x++)if (pre[j][x])pre[j + 1][x | v] = true;if (i < k - 1)continue;for (int x = 0; x < MX; x++)if (pre[k][x])for (int y = 0; y < MX; y++)if (suf[i + 1][y])ans = max(ans, x ^ y);}return ans;}
};
// @lc code=end

复杂度分析

时间复杂度：O(nkU+nU²），其中 n 是数组 nums 的长度，U 是数组 nums 所有元素的 OR，本题至多为 2⁷−1。DP 是 O(nkU) 的，计算 XOR 最大值是 O(U²) 的。

空间复杂度：O(nU），其中 n 是数组 nums 的长度，U 是数组 nums 所有元素的 OR，本题至多为 2⁷−1。

题目4：3288. 最长上升路径的长度

思路

将每个点按横坐标从小到大排序之后，我们就只要考虑纵坐标单调递增。因此问题就变成了经过某个点的最长上升子序列有多长。

经过某个点的最长上升子序列，可以分成以它为终点的、从左到右看的最长上升子序列，加上以它为终点的、从右到左看的最长下降子序列。

注：最长上升 / 下降子序列问题可以用二分查找求解。

代码

/** @lc app=leetcode.cn id=3288 lang=cpp** [3288] 最长上升路径的长度*/// @lc code=start
class Solution
{
public:int maxPathLength(vector<vector<int>> &coordinates, int k){int n = coordinates.size();vector<array<int, 3>> vec;for (int i = 0; i < n; i++)vec.push_back({coordinates[i][0], coordinates[i][1], i});sort(vec.begin(), vec.end(),[&](array<int, 3> &a, array<int, 3> &b){if (a[0] != b[0])return a[0] < b[0];elsereturn a[1] > b[1];});int ans = -1;// 以规定点为终点的，从左到右看的最长上升子序列vector<int> dp(n + 1, INT_MAX);dp[0] = INT_MIN;for (int i = 0; i < n; i++){int head = 0, tail = n;while (head < tail){int mid = (head + tail + 1) >> 1;if (dp[mid] < vec[i][1])head = mid;elsetail = mid - 1;}dp[head + 1] = vec[i][1];if (vec[i][2] == k){ans += head + 1;break;}}// 以规定点为终点的，从右到左看的最长下降子序列fill(dp.begin() + 1, dp.end(), INT_MIN);dp[0] = INT_MAX;for (int i = n - 1; i >= 0; i--){int head = 0, tail = n;while (head < tail){int mid = (head + tail + 1) >> 1;if (dp[mid] > vec[i][1])head = mid;elsetail = mid - 1;}dp[head + 1] = vec[i][1];if (vec[i][2] == k){ans += head + 1;break;}}return ans;}
};
// @lc code=end

复杂度分析

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

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