leetcode biweekly contest 120

算是比较简单的双周赛的题目了，T3 有一些思考的性质的题目，其余都是简单题目。

2970. 统计移除递增子数组的数目 I

给你一个下标从 0 开始的正整数数组 nums 。

如果 nums 的一个子数组满足：移除这个子数组后剩余元素 严格递增 ，那么我们称这个子数组为 移除递增 子数组。比方说，[5, 3, 4, 6, 7] 中的 [3, 4] 是一个移除递增子数组，因为移除该子数组后，[5, 3, 4, 6, 7] 变为 [5, 6, 7] ，是严格递增的。

请你返回 nums 中 移除递增 子数组的总数目。

注意，剩余元素为空的数组也视为是递增的。

子数组 指的是一个数组中一段连续的元素序列。

示例 1：

1
2
3

输入：nums = [1,2,3,4]
输出：10
解释：10 个移除递增子数组分别为：[1], [2], [3], [4], [1,2], [2,3], [3,4], [1,2,3], [2,3,4] 和 [1,2,3,4]。移除任意一个子数组后，剩余元素都是递增的。注意，空数组不是移除递增子数组。

示例 2：

输入：nums = [6,5,7,8]
输出：7
解释：7 个移除递增子数组分别为：[5], [6], [5,7], [6,5], [5,7,8], [6,5,7] 和 [6,5,7,8] 。
nums 中只有这 7 个移除递增子数组。

示例 3：

1
2
3

输入：nums = [8,7,6,6]
输出：3
解释：3 个移除递增子数组分别为：[8,7,6], [7,6,6] 和 [8,7,6,6] 。注意 [8,7] 不是移除递增子数组因为移除 [8,7] 后 nums 变为 [6,6] ，它不是严格递增的。

提示：

1 <= nums.length <= 50
1 <= nums[i] <= 50

地址

https://leetcode.cn/contest/biweekly-contest-120/problems/count-the-number-of-incremovable-subarrays-i/

题意

模拟

思路

题目比较有意思的题目，其实我们仔细分析一下，去掉一个数组中的一个连续子数组使得数组中剩余的元素严格递增，实际我们有三种去除方法：

去掉数组中的前 $x$ 个元素，使得剩余元素 $nums[{x+1}\cdots{n-1}]$ 严格递增；
去掉数组中的后 $x$ 个元素，使得剩余元素 $nums[{0}\cdots{n-x-1}]$ 严格递增；
去掉数组中间的 $x$ 个元素，使得剩余元素 $nums[{0}\cdots{i}]，nums[{i+x+1}\cdots{n-1}]$ 严格递增；
根据以上分析，我们分别检测这三种情况：
去掉前面的元素，此时我们求出数组后部最长的严格递增的元素数组为 $nums[r\cdots{n-1}]$，此时可以构成的严格递增子数组可以为: $nums[r\cdots n-1] \\ nums[r + 1\cdots n-1] \\ nums[r + 2\cdots n-1] \\ \cdots \\ nums[n-1] \\$ 一共可以有 $n-r$ 个严格递增子数组；
去掉后面的元素，此时我们求出数组前部最长的严格递增的元素数组为 $nums[0\cdots{l}]$，此时可以构成的严格递增子数组可以为: $nums[0\cdots l] \\ nums[0\cdots l-1] \\ nums[0\cdots l-2] \\ \cdots \\ nums[0] \\$ 一共可以有 $l + 1$ 个严格递增子数组；
去掉中间的元素，此时假设数组的前半分数数组为 $nums[0 \cdots l]$，后半部分数组为 $nums[r \cdots n-1]$，此时需要严格保证
- $nums[0 \cdots l]$ 严格递增；
- $nums[r \cdots n-1]$ 严格递增；
- $nums[r] > nums[l]$；
  实际此时我们可以用双指针，$l$ 指向数组的前半部分结尾， $r$ 指向后半部分的开头，此时移动左侧 $l$ 后，看存在多少 $r$ 满足 $nums[r] > nums[l]$;

复杂度分析：

时间复杂度：$O(n)$，其中 $n$ 表示给定数组的长度。
空间复杂度：$O(1)$。

代码

class Solution:
    def incremovableSubarrayCount(self, nums: List[int]) -> int:
        n = len(nums)
        res = 1
        left, right = 1, n - 1
        while left < len(nums) and nums[left] > nums[left - 1]:
            left += 1
        while right >= 1 and nums[right - 1] < nums[right]:
            right -= 1
            
        if left == n:
            return (n  + 1) * n // 2
        else:
            l, r = left, n - right
            res += l + r
            i, j = 0, right
            while i < left:
                while j < n and nums[j] <= nums[i]:
                    j += 1
                res += n - j
                i += 1
        return res

2973. 树中每个节点放置的金币数目

给你一棵 n 个节点的无向树，节点编号为 0 到 n - 1 ，树的根节点在节点 0 处。同时给你一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。

给你一个长度为 n 下标从 0 开始的整数数组 cost ，其中 cost[i] 是第 i 个节点的开销。

你需要在树中每个节点都放置金币，在节点 i 处的金币数目计算方法如下：

如果节点 i 对应的子树中的节点数目小于 3 ，那么放 1 个金币。
否则，计算节点 i 对应的子树内 3 个不同节点的开销乘积的 最大值 ，并在节点 i 处放置对应数目的金币。如果最大乘积是负数，那么放置 0 个金币。

请你返回一个长度为 n 的数组 coin ，coin[i]是节点 i 处的金币数目。

示例 1：

1
2
3

输入：edges = [[0,1],[0,2],[0,3],[0,4],[0,5]], cost = [1,2,3,4,5,6]
输出：[120,1,1,1,1,1]
解释：在节点 0 处放置 6 * 5 * 4 = 120 个金币。所有其他节点都是叶子节点，子树中只有 1 个节点，所以其他每个节点都放 1 个金币。

示例 2：

输入：edges = [[0,1],[0,2],[1,3],[1,4],[1,5],[2,6],[2,7],[2,8]], cost = [1,4,2,3,5,7,8,-4,2]
输出：[280,140,32,1,1,1,1,1,1]
解释：每个节点放置的金币数分别为：
- 节点 0 处放置 8 * 7 * 5 = 280 个金币。
- 节点 1 处放置 7 * 5 * 4 = 140 个金币。
- 节点 2 处放置 8 * 2 * 2 = 32 个金币。
- 其他节点都是叶子节点，子树内节点数目为 1 ，所以其他每个节点都放 1 个金币。

示例 3：

1
2
3

输入：edges = [[0,1],[0,2]], cost = [1,2,-2]
输出：[0,1,1]
解释：节点 1 和 2 都是叶子节点，子树内节点数目为 1 ，各放置 1 个金币。节点 0 处唯一的开销乘积是 2 * 1 * -2 = -4 。所以在节点 0 处放置 0 个金币。

提示：

2 <= n <= 2 * 104
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
cost.length == n
1 <= |cost[i]| <= 104
edges 一定是一棵合法的树。

地址

https://leetcode.cn/contest/biweekly-contest-120/problems/find-polygon-with-the-largest-perimeter/

题意

数学问题 + 贪心

思路

复杂度分析：

时间复杂度：$O(n \log n)$，其中 $n$ 表示给定数组的长度。
空间复杂度：$O(n)$。

代码

class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        n = len(nums)
        nums.sort()
        psum = [0] * (n + 1)
        for i in range(n):
            psum[i + 1] = psum[i] + nums[i]
        for i in range(n - 1, 1, -1):
            if psum[i + 1] > 2 * nums[i]:
                return psum[i + 1]
        return -1

2972. 统计移除递增子数组的数目 II

给你一个下标从 0 开始的正整数数组 nums 。

请你返回 nums 中 移除递增 子数组的总数目。

注意，剩余元素为空的数组也视为是递增的。

子数组 指的是一个数组中一段连续的元素序列。

示例 1：

1
2
3

输入：nums = [1,2,3,4]
输出：10
解释：10 个移除递增子数组分别为：[1], [2], [3], [4], [1,2], [2,3], [3,4], [1,2,3], [2,3,4] 和 [1,2,3,4]。移除任意一个子数组后，剩余元素都是递增的。注意，空数组不是移除递增子数组。

示例 2：

输入：nums = [6,5,7,8]
输出：7
解释：7 个移除递增子数组分别为：[5], [6], [5,7], [6,5], [5,7,8], [6,5,7] 和 [6,5,7,8] 。
nums 中只有这 7 个移除递增子数组。

示例 3：

1
2
3

输入：nums = [8,7,6,6]
输出：3
解释：3 个移除递增子数组分别为：[8,7,6], [7,6,6] 和 [8,7,6,6] 。注意 [8,7] 不是移除递增子数组因为移除 [8,7] 后 nums 变为 [6,6] ，它不是严格递增的。

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 109

地址

https://leetcode.cn/contest/biweekly-contest-120/problems/count-the-number-of-incremovable-subarrays-ii/

题意

贪心 + 数学

思路

题目比较有意思的题目，其实我们仔细分析一下，去掉一个数组中的一个连续子数组使得数组中剩余的元素严格递增，实际我们有三种去除方法：

去掉数组中的前 $x$ 个元素，使得剩余元素 $nums[{x+1}\cdots{n-1}]$ 严格递增；
去掉数组中的后 $x$ 个元素，使得剩余元素 $nums[{0}\cdots{n-x-1}]$ 严格递增；
去掉数组中间的 $x$ 个元素，使得剩余元素 $nums[{0}\cdots{i}]，nums[{i+x+1}\cdots{n-1}]$ 严格递增；
根据以上分析，我们分别检测这三种情况：
去掉前面的元素，此时我们求出数组后部最长的严格递增的元素数组为 $nums[r\cdots{n-1}]$，此时可以构成的严格递增子数组可以为: $nums[r\cdots n-1] \\ nums[r + 1\cdots n-1] \\ nums[r + 2\cdots n-1] \\ \cdots \\ nums[n-1] \\$ 一共可以有 $n-r$ 个严格递增子数组；
去掉后面的元素，此时我们求出数组前部最长的严格递增的元素数组为 $nums[0\cdots{l}]$，此时可以构成的严格递增子数组可以为: $nums[0\cdots l] \\ nums[0\cdots l-1] \\ nums[0\cdots l-2] \\ \cdots \\ nums[0] \\$ 一共可以有 $l + 1$ 个严格递增子数组；
去掉中间的元素，此时假设数组的前半分数数组为 $nums[0 \cdots l]$，后半部分数组为 $nums[r \cdots n-1]$，此时需要严格保证
- $nums[0 \cdots l]$ 严格递增；
- $nums[r \cdots n-1]$ 严格递增；
- $nums[r] > nums[l]$；
  实际此时我们可以用双指针，$l$ 指向数组的前半部分结尾， $r$ 指向后半部分的开头，此时移动左侧 $l$ 后，看存在多少 $r$ 满足 $nums[r] > nums[l]$;

复杂度分析：

时间复杂度：$O(n)$，其中 $n$ 表示给定数组的长度。
空间复杂度：$O(1)$。

代码

class Solution:
    def incremovableSubarrayCount(self, nums: List[int]) -> int:
        n = len(nums)
        res = 1
        left, right = 1, n - 1
        while left < len(nums) and nums[left] > nums[left - 1]:
            left += 1
        while right >= 1 and nums[right - 1] < nums[right]:
            right -= 1
            
        if left == n:
            return (n  + 1) * n // 2
        else:
            l, r = left, n - right
            res += l + r
            i, j = 0, right
            while i < left:
                while j < n and nums[j] <= nums[i]:
                    j += 1
                res += n - j
                i += 1
        return res

100123. 执行操作使频率分数最大

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

你可以对数组执行至多 k 次操作：

从数组中选择一个下标 i ，将 nums[i] 增加或者减少 1 。

最终数组的频率分数定义为数组中众数的频率。

请你返回你可以得到的最大频率分数。

众数指的是数组中出现次数最多的数。一个元素的频率指的是数组中这个元素的出现次数。

示例 1：

输入：nums = [1,2,6,4], k = 3
输出：3
解释：我们可以对数组执行以下操作：
- 选择 i = 0 ，将 nums[0] 增加 1 。得到数组 [2,2,6,4] 。
- 选择 i = 3 ，将 nums[3] 减少 1 ，得到数组 [2,2,6,3] 。
- 选择 i = 3 ，将 nums[3] 减少 1 ，得到数组 [2,2,6,2] 。
元素 2 是最终数组中的众数，出现了 3 次，所以频率分数为 3 。
3 是所有可行方案里的最大频率分数。

示例 2：

1
2
3

输入：nums = [1,4,4,2,4], k = 0
输出：3
解释：我们无法执行任何操作，所以得到的频率分数是原数组中众数的频率 3 。

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 109
0 <= k <= 1014

地址

https://leetcode.cn/contest/weekly-contest-376/problems/apply-operations-to-maximize-frequency-score/

题意

树上dp

思路

题目首先是个比较简单的题目，不晓得为啥标记为难题，首先可以知道一点，子数中 $3$ 个不同节点的乘积的最大值可以以下两种情况构成：

值为整数的最大的 $3$ 个值相乘；
正数的最大值乘以负数最小的两个值相乘；
由于只有上述两种情况，因此我们每次遍历时返回当前节点为根的子树中的 $5$ 个节点的值:
正数最大的三个值；
负数最大的两个值；
然后求得当前子树需要放置的金币数目。

复杂度分析:

时间复杂度：$O(n)$，其中 $n$ 表示树中节点的数目;
空间复杂度：$O(\log n)$，其中 $n$ 表示树中节点的数目;

代码

[sol1-C++]

class Solution {
public:
    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {
        int n = cost.size();
        vector<vector<int>> graph(n);
        vector<int> child(n);
        vector<long long> coins(n);
        
        for (auto v : edges) {
            graph[v[0]].emplace_back(v[1]);
            graph[v[1]].emplace_back(v[0]);
        }
        
        function<int(int, int)> dfs1 = [&](int root, int parent) {
            int res = 1;
            for (auto v : graph[root]) {
                if (v == parent) continue;
                res += dfs1(v, root);
            }
            child[root] = res;
            return res;
        };
        
        function<vector<vector<int>>(int, int)> dfs2 = [&](int root, int parent) {
            vector<int> pos(3, 0);
            vector<int> neg(3, 0);
            if (cost[root] > 0) {
                pos.emplace_back(cost[root]);
            } else {
                neg.emplace_back(cost[root]);
            }
            
            for (auto v : graph[root]) {
                if (v == parent) continue;
                auto vec = dfs2(v, root);
                pos.insert(pos.end(), vec[0].begin(), vec[0].end());
                neg.insert(neg.end(), vec[1].begin(), vec[1].end());
            }
            sort(pos.begin(), pos.end(), [](int x, int y) {
                return x > y;
            });
            sort(neg.begin(), neg.end());
            vector<vector<int>> res(2, vector<int>(3));
            for (int i = 0; i < 3; i++) {
                res[0][i] = pos[i];
                res[1][i] = neg[i];
            }
            if (child[root] < 3) {
                coins[root] = 1;
            } else {
                coins[root] = max((long long)pos[0] * pos[1] * pos[2], (long long)pos[0] * neg[0] * neg[1]);
            }
            return res;
        };
        
        dfs1(0, -1);
        dfs2(0, -1);
        return coins;
    }
};

欢迎关注和打赏，感谢支持！

关注我的博客: https://mike-box.github.io/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu

力扣周赛

#题解 #力扣周赛赛

leetcode biweekly contest 120

http://example.com/2026/09/08/力扣周赛题解/169/

Author

Mike Meng

Posted on

September 8, 2026

Licensed under

leetcode contest 375 Previous

leetcode contest 376 Next