文章目录
🍋什么是贪心算法？
贪心算法：是一种思想，解答要根据具体题目来编写代码，它让每一步都是局部最优的方案。
🍋1. 分配饼干
题目描述链接
https://leetcode.cn/problems/assign-cookies/
题目特点
寻找最优解，一维数组。
代码实现
贪心大致思路：先边界判断，直接排序，后找到需要的情况返回。
public int findContentChildren(int[] g, int[] s) {
if (g==null || s==null){
return 0;
}
Arrays.sort(g);
Arrays.sort(s);
int i=0,j=0;
while(i<g.length&&j<s.length){
if (g[i]<=s[j]){
j++;
}
i++;
}
return j;
}
时间复杂度和空间复杂度
时间复杂度：O(NlogN)；
空间复杂度：O(N)。
🍋2. 不重叠的区间个数
题目描述链接
https://leetcode.cn/problems/non-overlapping-intervals/
题目特点
寻找最优解，一维数组。
代码实现
贪心大致思路：先边界判断，直接排序，后找到需要的情况返回。
public int eraseOverlapIntervals(int[][] intervals) {
//边界判断
if (intervals==null){
return 0;
}
//排序
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return (o1[1]<o2[1])?-1:(o1[1]==o2[1]?0:1);
}
});
//找到符合条件的情况
int ans=0;
int right=intervals[0][1];
for (int i = 0; i < intervals.length; i++) {
if (intervals[i][0]>=right){
ans++;
right=intervals[i][1];
}
}
return intervals.length-ans;
}
时间复杂度和空间复杂度
时间复杂度：O(NlogN)；
空间复杂度：O(N)。
🍋3. 投飞镖刺破气球
题目描述链接
https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/
题目特点
寻找最优解，一维数组。
代码实现
贪心大致思路：先边界判断，直接排序，后找到需要的情况返回。
public int findMinArrowShots(int[][] points) {
//先判断边界条件
if (points==null){
return 0;
}
//排序
Arrays.sort(points, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[1]<o2[1]?-1:(o1[1]==o2[1]?0:1);
}
});
//找到符合条件的情况
int ans=1;
int index=points[0][1];
for (int i = 0; i < points.length; i++) {
if(index<points[i][0]){
ans++;
index=points[i][1];
}
}
return ans;
}
时间复杂度和空间复杂度
时间复杂度：O(NlogN)；
空间复杂度：O(N)。
🍋4. 根据身高和序号重组队列
题目描述链接
https://leetcode.cn/problems/queue-reconstruction-by-height/
题目特点
寻找正确队列的组合。
代码实现
贪心大致思路：先边界判断，直接排序，后找到需要的情况返回。
public static int[][] reconstructQueue1(int[][] people) {
if (people==null){
return people;
}
//根据身高降序排列，K值升值排列
Arrays.sort(people, (a, b) -> a[0] == b[0]? a[1] - b[1] : b[0] - a[0]);
List<int[]> list = new ArrayList<>();
//遍历people,添加进list
for(int[] secondArray : people){
list.add(secondArray[1], secondArray);
}
//插入完成， 输入到int[][]输出
//将list变成二维数组
return list.toArray(new int[list.size()][]);
}
时间复杂度和空间复杂度
时间复杂度：O(NlogN)；
空间复杂度：O(N)。
🍋5. 买卖股票最大的收益
题目描述链接
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/
题目特点
不考虑前一天的情况，买入最低，卖出最高，与天数有关，不需要排序。
代码实现
贪心大致思路：先判断边界条件，不需要排序，因为需要用到索引，处理遍历一维数组就搞定了。
public static int maxProfit(int[] prices) {
//先判断边界条件
if (prices.length==0||prices.length==1){
return 0;
}
//排序，不需要
//处理
int minBuy=prices[0];
int max=0;
for (int i = 1; i < prices.length; i++) {
if (minBuy>prices[i]){
minBuy=prices[i];
}else{
max=Math.max(max,prices[i]-minBuy);
}
}
return max;
}
时间复杂度和空间复杂度
时间复杂度：O(N)；
空间复杂度：O(1)。
🍋6. 买卖股票的最大收益 II
题目描述链接
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
题目特点
与第五题相比，可以随买随卖，可以购买n次。
代码实现
贪心大致思路：先判断边界条件，不需要排序，因为需要用到索引，处理遍历一维数组就搞定了。
public static int maxProfit(int[] prices) {
//先判空
if (prices.length == 0 || prices.length == 1) {
return 0;
}
//与索引值绑定很深，不需要排序
//处理
int minBuy = prices[0];
int max = 0;
int sum = 0;
for (int i = 1; i < prices.length; i++) {
if (minBuy > prices[i] || prices[i - 1] > prices[i]) {
minBuy = prices[i];
sum += max;
max = 0;
} else {
max = Math.max(max, prices[i] - minBuy);
}
}
sum += max;
return sum;
}
改进版本：
public static int maxProfit1(int[] prices) {
int max=0;
for (int i = 1; i < prices.length; i++) {
if (prices[i]>prices[i-1]){
max += prices[i]-prices[i-1];
}
}
return max;
}
时间复杂度和空间复杂度
时间复杂度：O(N)VSO(N)；
空间复杂度：O(1)VS(1)。
🍋7. 种植花朵
题目描述链接
https://leetcode.cn/problems/can-place-flowers/
题目特点
所走的每一步都要满足局部最优。
代码实现
贪心算法：
public static boolean canPlaceFlowers2(int[] flowerbed, int n) {
int len=flowerbed.length;
int cnt=0;
for (int i = 0; i < len; i++) {
if (flowerbed[i]==1){
continue;
}
int pre= i==0?0:flowerbed[i-1];
int next= i==len-1?0:flowerbed[i+1];
if (pre==0&&next==0){
cnt++;
flowerbed[i]=1;
}
}
return cnt>=n;
}
时间复杂度和空间复杂度
时间复杂度：O(N)，
空间复杂度：O(1)。
🍋8. 判断是否为子序列
题目描述链接
https://leetcode.cn/problems/is-subsequence/
题目特点
一维数组，找对应的字串。
代码实现
暴力破解：
public boolean isSubsequence(String s, String t) {
int count=0;
int index=0;
for (int i = 0; i < s.length(); i++) {
for (int j = index; j < t.length(); j++) {
if (s.charAt(i)==t.charAt(j)){
count++;
index=j+1;
break;
}
}
}
return count==s.length();
}
巧用字符串的indexof方法：
public boolean isSubsequence(String s, String t) {
int index=-1;
for (char c:s.toCharArray()) {
index=t.indexOf(c,index+1);
if (index==-1){
return false;
}
}
return true;
}
时间复杂度和空间复杂度
时间复杂度：O(N2)VSO(N2)；
空间复杂度：O(1)VSO(1)。
🍋9. 修改一个数成为非递减数组
题目描述链接
https://leetcode.cn/problems/non-decreasing-array/
题目特点
一维数组，最多修改一次就符合条件意思。
代码实现
贪心：
public boolean checkPossibility(int[] nums) {
int cnt=0;
for (int i = 1; i < nums.length; i++) {
if (nums[i]>=nums[i-1]){
continue;
}
cnt++;
if (i-2>=0&&nums[i-2]>nums[i]){
nums[i]=nums[i-1];// 3 ,4 ,1
}else{
nums[i-1]=nums[i];// 4, 2, 3
}
}
return cnt<=1 ;
}
时间复杂度和空间复杂度
时间复杂度：O(N)；
空间复杂度：O(1)。
🍋10. 子数组最大的和
题目描述链接
https://leetcode.cn/problems/maximum-subarray/
题目特点
一维数组，往下走的每一步都需要最优的。
代码实现
贪心：
public static int maxSubArray1(int[] nums) {
//边界判断
if (nums==null||nums.length==0){
return 0;
}
int preSum = nums[0];
int maxSum = preSum;
for (int i = 1; i < nums.length; i++) {
preSum = preSum > 0 ? preSum + nums[i] : nums[i];
maxSum = Math.max(maxSum, preSum);
}
return maxSum;
}
时间复杂度和空间复杂度
时间复杂度：O(N)；
空间复杂度：O(1)。
🍋11. 分隔字符串使同种字符出现在一起
题目描述链接
https://leetcode.cn/problems/partition-labels/
题目特点
一维数组，要求尽可能多的问题。
代码实现
贪心：走的每一步都是最优的，根据题目意思编码代码。
public List<Integer> partitionLabels(String s) {
int[] last = new int[26];
int length = s.length();
for (int i = 0; i < length; i++) {
last[s.charAt(i) - 'a'] = i;
}
List<Integer> partition = new ArrayList<Integer>();
int start = 0, end = 0;
for (int i = 0; i < length; i++) {
end = Math.max(end, last[s.charAt(i) - 'a']);
if (i == end) {
partition.add(end - start + 1);
start = end + 1;
}
}
return partition;
}
时间复杂度和空间复杂度
时间复杂度：O(N^2)；
空间复杂度：O(1-N)。
🍋题型总结
使用条件：
- 出现最大、最小、尽可能多、尽可能少等字眼，可能要用到贪心算法；
- 大部分的贪心算法题目，虽然是一维数组，但是数组的下标有一定的用处；
- 全局最优解可以通过多个局部最优解得到（最重要的一点）。