# Javascript数据结构与算法之贪心算法
# 贪心算法的定义
贪心算法就是一种比较简单的算法。贪心算法总是会选择当下的最优解，而不去考虑这一次的选择会不会对未来的选择造成影响。使用贪心算法通常表明，实现者希望做出的这一 系列局部“最优”选择能够带来最终的整体“最优”选择。如果是这样的话，该算法将会 产生一个最优解，否则，则会得到一个次优解。然而，对很多问题来说，寻找最优解很麻烦，这么做不值得，所以使用贪心算法就足够了。
# 贪心算法的应用练习
leetcode题目练习：
- 买卖股票的最佳时机II【简单】
- 柠檬水找零【简单】
- 跳跃游戏 II【困难】
# 1. 买卖股票的最佳时机II
# 题目描述：
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
# 示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
# 示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
# 示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
# 提示：
1 <= prices.length <= 3 * 10 ^ 4
0 <= prices[i] <= 10 ^ 4
# 解题思路：
循环每一个i都获取当前能获得的最大利润 代码实现：
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
let sum = 0;
let min = prices[0]; // 把第一个当成最小值
for(let i = 1; i < prices.length; i++) {
if(prices[i] > min) { // 碰到比他大的就卖 然后把值赋成这个值
sum += (prices[i] - min);
min = prices[i];
} else { // 碰到比他小的就买进
min = prices[i];
}
}
return sum;
};
# 2. 柠檬水找零
# 题目描述：
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。
顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
# 示例 1：
输入：[5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。
# 示例 2：
输入：[5,5,10]
输出：true
# 示例 3：
输入：[10,10]
输出：false
# 示例 4：
输入：[5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。
# 提示：
- 0 <= bills.length <= 10000
- bills[i] 不是 5 就是 10 或是 20
# 解题思路：
代码实现：
/**
* @param {number[]} bills
* @return {boolean}
*/
var lemonadeChange = function(bills) {
// 能用值存储就别用引用存储
let five = 0, ten = 0, twn = 0;
for(let i = 0; i < bills.length; i++) {
if(bills[i] === 5) {
five++; // 5块钱 直接存
} else if(bills[i] === 10) {
ten++;
if(five > 0) {
five--;
} else {
return false; // 没有5块钱
}
} else if(bills[i] === 20){
twn++;
if(ten > 0 && five > 0) {
ten--;
five--;
} else if(five > 2) {
five -= 3;
} else {
return false;
}
}
}
return true;
};
# 3. 跳跃游戏 II
# 题目描述：
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
# 示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
# 说明:
假设你总是可以到达数组的最后一个位置。
# 解题思路：
代码实现：
/**
* @param {number[]} nums
* @return {number}
*/
const jump = function(nums) {
// 1. 每次循环找最大能到的 step控制走了几步 如果最大能到的都还没到 那对step没影响
if(nums.length < 2) return 0; // 只有一个数不用走就到了
let maxJump = 0;
let last_maxJump = 0; // last_maxJump是上一个最大能到到位置
let step = 0;
for(let i = 0; i < nums.length; i++) {
maxJump = Math.max(nums[i] + i, maxJump);
if(last_maxJump === i) { // last_maxJump === i说明已经循环到上一个最大能到达的位置 step得加1了
last_maxJump = maxJump;
step++;
}
if(last_maxJump >= nums.length - 1) {
return step;
}
}
};