贪心算法三道经典题（买卖股票，分发饼干）
贪心算法
贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
步骤：
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
分发饼干
LeetCode原题
找满足孩子数量的最大值———最优解问题
什么时候最优？孩子都被分配最小的符合条件的饼干
所以把问题拆解成：找到目前未被满足的需求最小的孩子，分配他最小的符合要求的饼干
使数组有序再遍历即可
class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int m = g.length, n = s.length;int count = 0;for(int i =0,j=0;i<m&&j<n;i++,j++){while(j<n&&g[i]>s[j]){j++;}if(j<n){count++;}}return count;}
}
买卖股票的最佳时机
LeetCode原题
分析题目：
找最大利润————最优解问题
什么时候利润最大？买入价格和未来最高价格的差值最大时，利润最大
分解问题：找到每一天买入价格和未来最高价格的差值，比较即可
class Solution {public int maxProfit(int[] prices) {int maxprofit = 0;for(int i =0;i<prices.length;i++){int price = prices[i];int maxprice = prices[i];for(int j =i+1;j<prices.length;j++){if(maxprice<prices[j]){maxprice = prices[j];}}int profit =maxprice-price;if(maxprofit<profit){maxprofit = profit;}}return maxprofit;}
}
上述方法时间复杂度较高，如何简化？
简化用一个变量遍历过的价格的最小值，因为只能买卖一次，所以无论如何，从最低点买都是利润最高的
public class Solution {public int maxProfit(int prices[]) {int minprice = prices[0];int maxprofit = 0;for (int i = 0; i < prices.length; i++) {if (prices[i] < minprice) {minprice = prices[i];} else if (prices[i] - minprice > maxprofit) {maxprofit = prices[i] - minprice;}}return maxprofit;}
}
买卖股票的最佳时机 II
LeetCode原题
为什么能够多次买入卖出，代码反而更简单了？
只需要考虑前一天和后一天的价格差即可
假设i天买入，后两天价格都上升了，i+1天卖了之后，i+1天再原价买入即可————只要下一天价格上升，就可以买入再买
class Solution {public int maxProfit(int[] prices) {int ans = 0;int n = prices.length;for (int i = 1; i < n; ++i) {ans += Math.max(0, prices[i] - prices[i - 1]);}return ans;}
}