贪心算法所采用的策略，是保证每次操作都是局部最优，从而使最后结果是全局最优。
1.
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
关键：两次遍历，从左往右，大的加一，从右往左，大的加一。
代码：
class Solution { public: int candy(vector<int>& ratings) { int m=ratings.size(); vector<int> nums(m,1); if(m<2) return m; int i; for(i=1;i<m;i++){ if(ratings[i]>ratings[i-1]){ nums[i]=nums[i-1]+1; } } for(i=m-1;i>0;i--){ if(ratings[i-1]>ratings[i]){ nums[i-1]=max(nums[i-1],nums[i]+1); } } return accumulate(nums.begin(),nums.end(),0); } }; 2.字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
示例：
输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
解答：由于同一个字母只能出现在同一个片段，显然同一个字母的第一次出现的下标位置和最后一次出现的下标位置必须出现在同一个片段。因此需要遍历字符串，得到每个字母最后一次出现的下标位置。
在得到每个字母最后一次出现的下标位置之后，可以使用贪心的方法将字符串划分为尽可能多的片段，具体做法如下。
从左到右遍历字符串，遍历的同时维护当前片段的开始下标 start 和结束下标 end，初始时 start=end=0。对于每个访问到的字母 ，得到当前字母的最后一次出现的下标位置 cend，则当前片段的结束下标一定不会小于 end，因此令 end=max(end,end
c
)。
当访问到下标 end 时，当前片段访问结束，当前片段的下标范围[start,end]，长度为 end−start+1，将当前片段的长度添加到返回值，然后令 start=end+1，继续寻找下一个片段。
重复上述过程，直到遍历完字符串。
代码：
class Solution {
public:
vector<int> partitionLabels(string s) {
int last[26];
int length = s.size();
for (int i = 0; i < length; i++) {
last[s[i] - 'a'] = i;
}
vector<int> partition;
int start = 0, end = 0;
for (int i = 0; i < length; i++) {
end = max(end, last[s[i] - 'a']);
if (i == end) {
partition.push_back(end - start + 1);
start = end + 1;
}
}
return partition;
}
};
3.
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有一股股票。你也可以先购买，然后在同一天出售。
返回你能获得的最大利润 。
示例 1：
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。
解答:
代码:
class Solution { public: int maxProfit(vector<int>& prices) { int ans=0; for(int i=1;i<prices.size();i++){ ans+=max(0,prices[i]-prices[i-1]); } return ans; } }; 标签：片段,下标,nums,int,start,算法,end,贪心 From： https://www.cnblogs.com/LCAB/p/16815439.html