双向权衡问题相当于既要又要，依然是贪心的思路，先完成一个要求，在完成另一个要求。
也就是说用两个局部最优（一般第二个局部最优是在第一个的基础上进行），去完成全局最优。
135. 分发糖果
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
- 每个孩子至少分配到
1个糖果。 - 相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
思路：
先确定右边评分大于左边的情况（也就是从前向后遍历）
局部最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果
再确定左孩子大于右孩子的情况（从后向前遍历）
局部最优：相邻的孩子中，评分高的左孩子获得比右边孩子更多的糖果
在第一个局部最优的基础上（两者结合）：
vec_candy[i]=max(vec_candy[i],vec_candy[i+1]+1);//前者是从前向后遍历的结果，后者是当前结果
代码如下：
class Solution {
public:
int candy(vector<int>& ratings) {
vector<int> vec_candy(ratings.size(),1);
for(int i=1;i<ratings.size();i++){
if(ratings[i]>ratings[i-1]){//第一贪
vec_candy[i]=vec_candy[i-1]+1;
}
}
for(int i=ratings.size()-2;i>=0;i--){
if(ratings[i]>ratings[i+1]){//第二贪
vec_candy[i]=max(vec_candy[i],vec_candy[i+1]+1);
}
}
int res=0;
for(int x:vec_candy){
res+=x;
}
return res;
}
};
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
思路：
先按照身高来排序，从大到小排。
然后从前往后遍历，根据每人的k值插入到对应的位置。
代码如下：
class Solution {
public:
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
// 先按身高降序排列，如果身高相同，按k值升序排列
sort(people.begin(), people.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);//注意这里当相等时k大的排在后面
});
vector<vector<int>> result;
// 根据每个人的 k 值插入到对应的位置
for (const auto& person : people) {
result.insert(result.begin() + person[1], person);
}
return result;
}
};
暂无评论