【LeetCode周赛】LeetCode第368场周赛

元素和最小的山形三元组 I

给你一个下标从 0 开始的整数数组 nums 。
如果下标三元组 (i, j, k) 满足下述全部条件，则认为它是一个山形三元组 ：
i < j < k
nums[i] < nums[j] 且 nums[k] < nums[j]
请你找出nums中元素和最小的山形三元组，并返回其 元素和 。如果不存在满足条件的三元组，返回 -1 。

示例 1：

输入：nums = [8,6,1,5,3]
输出：9
解释：三元组 (2, 3, 4) 是一个元素和等于 9 的山形三元组，因为：

• 2 < 3 < 4
• nums[2] < nums[3] 且 nums[4] < nums[3]

这个三元组的元素和等于 nums[2] + nums[3] + nums[4] = 9 。可以证明不存在元素和小于 9 的山形三元组。

示例 2：

输入：nums = [5,4,8,7,10,2]
输出：13 解释：三元组 (1, 3, 5) 是一个元素和等于 13 的山形三元组，因为：

• 1 < 3 < 5
• nums[1] < nums[3] 且 nums[5] < nums[3]

这个三元组的元素和等于 nums[1] + nums[3] + nums[5] = 13 。可以证明不存在元素和小于 13 的山形三元组。

示例 3：

输入：nums = [6,5,4,3,4,5]
输出：-1
解释：可以证明 nums 中不存在山形三元组。

提示：
$3<=nums.length<=50$
$1<=nums[i]<=50$

分析：
因为数据范围很小，所以可以直接按照题目意思进行模拟，遍历每一个三元组，维护一个最小三元组的和即可。时间复杂度$O(n^3)$。
代码：

class Solution {
public:int minimumSum(vector<int>& nums) {int n=nums.size();int ans=INT_MAX;for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){for(int k=j+1;k<n;k++){if(nums[i]<nums[j]&&nums[k]<nums[j])ans=min(ans,nums[i]+nums[j]+nums[k]);}}}if(ans==INT_MAX)ans=-1;return ans;}
};

元素和最小的山形三元组 II

给你一个下标从 0 开始的整数数组 nums 。
如果下标三元组 (i, j, k) 满足下述全部条件，则认为它是一个山形三元组 ：
i < j < k
nums[i] < nums[j] 且 nums[k] < nums[j]
请你找出nums中元素和最小的山形三元组，并返回其 元素和 。如果不存在满足条件的三元组，返回 -1 。

示例 1：

输入：nums = [8,6,1,5,3]
输出：9
解释：三元组 (2, 3, 4) 是一个元素和等于 9 的山形三元组，因为：

• 2 < 3 < 4
• nums[2] < nums[3] 且 nums[4] < nums[3]

这个三元组的元素和等于 nums[2] + nums[3] + nums[4] = 9 。可以证明不存在元素和小于 9 的山形三元组。

示例 2：

输入：nums = [5,4,8,7,10,2]
输出：13 解释：三元组 (1, 3, 5) 是一个元素和等于 13 的山形三元组，因为：

• 1 < 3 < 5
• nums[1] < nums[3] 且 nums[5] < nums[3]

这个三元组的元素和等于 nums[1] + nums[3] + nums[5] = 13 。可以证明不存在元素和小于 13 的山形三元组。

示例 3：

输入：nums = [6,5,4,3,4,5]
输出：-1
解释：可以证明 nums 中不存在山形三元组。

提示：
$3<=nums.length<=10^5$
$1<=nums[i]<=10^8$

分析：
本题为第一题的加强版，数据范围扩大，使用题一的$O(n^3)$的方法会TLE，所以我们仔细思考题意，不难想到，要使得一个三元组的和最小，那么对于山顶i，找到i左边的最小值pre[i]，和i右边的最小值suf[i]，只要pre[i]和suf[i]同时都小于nums[i]的值，那么这就是以i为山顶的三元组的和的最小值。
所以我们可以先进行预处理，遍历一遍数组，维护一个前缀最小值和后缀最小值。时间复杂度为$O(n)$
代码：

class Solution {
public:int minimumSum(vector<int>& nums) {//对每个数找到其前面的最小数和后面的最小数int n = nums.size();vector<int>pre(n+1),suf(n+1);pre[0]=nums[0];suf[n-1]=nums[n-1];for(int i=1;i<n;i++)pre[i]=min(nums[i],pre[i-1]);for(int i=n-2;i>=0;i--)suf[i]=min(nums[i],suf[i+1]);int ans=INT_MAX;for(int i=0;i<n;i++){if(nums[i]>pre[i]&&nums[i]>suf[i])ans=min(ans,pre[i]+nums[i]+suf[i]);}if(ans==INT_MAX)ans=-1;return ans;}
};

合法分组的最少组数

给你一个长度为 n 下标从 0 开始的整数数组 nums 。
我们想将下标进行分组，使得 [0, n - 1] 内所有下标 i 都 恰好 被分到其中一组。
如果以下条件成立，我们说这个分组方案是合法的：
对于每个组 g ，同一组内所有下标在 nums 中对应的数值都相等。
对于任意两个组 g1 和 g2 ，两个组中 下标数量 的 差值不超过 1 。
请你返回一个整数，表示得到一个合法分组方案的 最少 组数。

示例 1：

输入：nums = [3,2,3,2,3]
输出：2
解释：一个得到 2 个分组的方案如下，中括号内的数字都是下标：
组 1 -> [0,2,4]
组 2 -> [1,3]
所有下标都只属于一个组。 组 1 中，nums[0] == nums[2] == nums[4]，所有下标对应的数值都相等。
组 2 中，nums[1] == nums[3] ，所有下标对应的数值都相等。
组 1 中下标数目为 3 ，组2 中下标数目为 2 。
两者之差不超过 1 。
无法得到一个小于 2 组的答案，因为如果只有 1 组，组内所有下标对应的数值都要相等。
所以答案为 2 。

示例 2：

输入：nums = [10,10,10,3,1,1]
输出：4
解释：一个得到 2 个分组的方案如下，中括号内的数字都是下标：
组 1 ->[0]
组 2 -> [1,2]
组 3 -> [3]
组 4 -> [4,5]
分组方案满足题目要求的两个条件。 无法得到一个小于 4组的答案。
所以答案为 4 。

提示：
$1<=nums.length<=10^5$
$1<=nums[i]<=10^9$

分析：
首先我们需要统计每个数字出现的次数，维护在cnt中。
如何判断一个数字可以拆分为k和k+1的组合呢？
比如说cnt[x]=13，k=4，那么13=4+4+4+1，多出来的这一个1可以丢进前面的某一个4中，同理11=4+4+3，不能由k和k+1构成，14=4+4+4+2=5+5+4，15=4+4+4+3=5+5+5，而16=4+4+4+4，不能由5表示了，可以想到，只要cnt[x]/k的值大于等于cnt[x]%k的值，那么其就可以由k和k+1来构成。
那么如何计算最小的分组呢？
不难理解，只要分出的k+1越多，那么分出的组数肯定就越少，即最少可以分出$\lceil \frac{cnt[x]}{k+1}\rceil$个组。
因为我们已经确定了能够拆分为k和k+1的组合，p=cnt[x]/k，v=cnt[x]%k，先拆成了p个k，剩下数字v，其实就是v有几个，那么就可以将多少个v个k加一变成k+1。所以直接除以k+1即可得到组数，上取整是因为如果除以k+1有余数，那么这个余数需要补充到有k个数，即组数会多一个。
比如15=5+5+5，16=5+5+5+1=4+4+4+4，13=5+5+3=5+4+4。
最后只需要从min(cnt[x])开始往下枚举k，找到一个满足要求的k即可返回结果。
时间复杂度：枚举cnt中最小的数为k，cnt的size为m，$mk\le n$，循环的次数最多为km，所以时间复杂度为$O(n)$。
代码：

class Solution {
public:int minGroupsForValidAssignment(vector<int>& nums) {int n = nums.size();unordered_map<int, int>mp;vector<int>cnt;for(int i = 0; i < n ; i++){mp[nums[i]]++;}for(auto &[k,v]:mp)cnt.push_back(v);sort(cnt.begin(),cnt.end());int min_num=cnt[0];//枚举最小的组do{int ans = 0;if(min_num==0)break;for(auto x:cnt){int p = x / min_num;int v = x % min_num;if(p >= v)ans += (x + min_num) / (min_num + 1);else{ans = 0;break;}}if(ans)return ans;}while(min_num--);return 0;}};