如果找出局部最优并可以推出全局最优，就是贪心，如果局部最优都没找出来，就不是贪心，可能是单纯的模拟。

感觉都是数组题，排序后和前一个数值作比较

11. 盛最多水的容器

双指针，有贪心的思想

  1. var maxArea = function(height) {
  2.    let left=0,right=height.length-1;
  3.    let result=0;
  4.    while(left<right){
  5.        let ans=Math.min(height[left],height[right])*(right-left)
  6.        result=Math.max(result,ans)
  7.        if(height[left]<=height[right]){
  8.            left++
  9.        }else{
  10.            right--;
  11.        }
  12.    }
  13.    return result;
  14. };

455. 分发饼干

这题有点常识判断。
排序，尽可能小饼干给小胃口的人吃

  1. var findContentChildren = function(g, s) {
  2.   //将g,s排序
  3.   g.sort((a,b)=>a-b);
  4.   s.sort((a,b)=>a-b);
  5.   let gi=0;;
  6.   for(let n of s){
  7.       if(n>=g[gi]){
  8.           gi++;
  9.       }
  10.   }
  11.   return gi;
  12. };

1005. K 次取反后最大化的数组和

这题有点常识判断。
贪心的思路，局部最优：让绝对值大的负数变为正数，当前数值达到最大，整体最优：整个数组和达到最大。
那么如果将负数都转变为正数了，K依然大于0，此时的问题是一个有序正整数序列，如何转变K次正负，让 数组和达到最大。那么又是一个贪心：局部最优：只找数值最小的正整数进行反转，当前数值可以达到最大。

  1. var largestSumAfterKNegations = function(nums, k) {
  2.   let newNums=nums.sort((a,b)=> a-b);
  3.   let count=k;
  4.   let sum=0;
  5.   for(let i=0;i<newNums.length;i++){
  6.       if(count>0 && newNums[i]<0){
  7.         newNums[i]*=-1  
  8.         count--
  9.       }
  10.       sum+=newNums[i]
  11.   }
  12.   if(count>0 && count%2!==0){
  13.     newNums=newNums.sort((a,b)=> a-b);;
  14.     sum-=2*newNums[0];
  15.   } 
  16.   return sum;
  18. };

860. 柠檬水找零

这题有点常识判断。
针对不同付钱5/10/20有不同找零策略，20时运用到贪心。
局部最优：遇到账单20，优先消耗美元10，如果不够，再消耗三个5，完成本次找零。全局最优：完成全部账单的找零。
因为美元10只能给账单20找零，而美元5可以给账单10和账单20找零，美元5更万能！

  1. /**
  2.  * @param {number[]} bills
  3.  * @return {boolean}
  4.  */
  5. var lemonadeChange = function(bills) {
  6.   let five=0,ten=0;
  7.   for(let i=0;i<bills.length;i++){
  8.      const bill=bills[i];
  9.      if(bill===5) five++;
  10.      if(bill===10){
  11.         if(five>0){
  12.             five--;
  13.             ten++;
  14.         }else{
  15.             return false;
  16.         }
  17.      }
  18.      if(bill===20){
  19.          if(ten>0 && five>0){
  20.             ten--;
  21.             five--;
  22.          }else if(five>2){
  23.             five=five-3;
  24.          }else{
  25.             return false;
  26.          }
  27.      }
  28.   }
  29.   return true;
  30. };

376. 摆动序列

局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。
整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。

感觉与买卖股票类似， 还可以用动态规划来做

  1. var wiggleMaxLength = function(nums) {
  2.   let count=0;
  3.   let pre=0,cur=0;
  4.   for(let i=1;i<nums.length;i++){
  5.      let cur=nums[i]-nums[i-1]
  6.      if(cur===0 || (cur>0 && pre>0 )|| (cur<0 && pre<0)) { 
  7.        //与前一个值作比较，不满足则跳过坡度上节点
  8.        count++;  
  9.      }else{
  10.        pre=cur;  //如果满足摆动，则更新pre
  11.      }
  13.   }
  14.   return nums.length-count;
  15. };

738. 单调递增的数字

局部最优：遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]—，然后strNum[i]给为9，可以保证这两位变成最大单调递增整数。
全局最优：得到小于等于N的最大单调递增的整数。
还需要考虑从前往后还是从后往前的遍历顺序

  1. var monotoneIncreasingDigits = function (n) {
  2.     let array = n.toString().split('').map((i) => {
  3.         return +i;
  4.     })
  5.     let flag = Infinity
  6.     for (let i = array.length - 2; i >= 0; i--) {
  7.         if (array[i] > array[i + 1]) {
  8.             flag = i + 1
  9.             array[i] = array[i] - 1;
  10.         }
  11.     }
  12.     for (let i = flag; i < array.length; i++) { //100的情况
  13.         array[i] = 9
  14.     }
  15.     return +array.join('')
  16. };

134. 加油站

局部最优：当前累加rest[j]的和curSum一旦小于0，起始位置至少要是j+1，因为从j开始一定不行。全局最优：找到可以跑一圈的起始位置。

  1. var canCompleteCircuit = function(gas, cost) {
  2.     let allSum=0;
  3.     let curSum=0;
  4.     let start=0;
  5.     for(let i=0;i<gas.length;i++){
  6.         curSum+=(gas[i]-cost[i])
  7.         allSum+=(gas[i]-cost[i])
  8.         if(curSum<0){
  9.             start=i+1
  10.             curSum=0;
  11.         }
  12.     }
  13.     if(allSum<0) return -1;
  14.     return start;
  15. };

两个维度权衡问题

在出现两个维度相互影响的情况时，两边一起考虑一定会顾此失彼，要先确定一个维度，再确定另一个一个维度。

135. 分发糖果

有点类似前后缀乘积那道题
这道题目一定是要确定一边之后，再确定另一边，例如比较每一个孩子的左边，然后再比较右边，如果两边一起考虑一定会顾此失彼。
先确定右边评分大于左边的情况（也就是从前向后遍历）
此时局部最优：只要右边评分比左边大，右边的孩子就多一个糖果，全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果。
再确定左孩子大于右孩子的情况（从后向前遍历）
最终全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。

  1. /**
  2.  * @param {number[]} ratings
  3.  * @return {number}
  4.  */
  5. var candy = function (ratings) {
  6.     const length = ratings.length
  7.     let result = Array(length).fill(1);
  8.     for (let i = 1; i < length; i++) { //从前向后遍历，如果右边的比左边的大
  9.         if (ratings[i] > ratings[i - 1]) {
  10.             result[i] = result[i - 1] + 1
  11.         }
  12.     }
  13.     let sum = result[length - 1];
  14.     for (let i = length - 2; i >= 0; i--) { //从后向前遍历，如果左边边的比右边的大
  15.         if (ratings[i] > ratings[i + 1]) {
  16.             result[i] = Math.max(result[i + 1] + 1, result[i]) //max为了防止[1,3,4,5,2] 11 这种情况
  17.         }
  18.         sum += result[i]
  20.     }
  21.     return sum;
  22. };

406. 根据身高重建队列

有身高和排序两个维度，简化成一个维度分别比较
局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性
全局最优：最后都做完插入操作，整个队列满足题目队列属性

  1. /**
  2.  * @param {number[][]} people
  3.  * @return {number[][]}
  4.  */
  5. var reconstructQueue = function (people) {
  6.     people.sort((a, b) => {
  7.         if (a[0] !== b[0]) {
  8.             return b[0] - a[0]
  9.         } else {
  10.             return a[1] - b[1]
  11.         }
  12.     })
  13.     let result = []
  14.     for (let i = 0; i < people.length; i++) {
  15.         result.splice(people[i][1], 0, people[i])
  16.     }
  17.     return result;
  18. };

区间问题

55. 跳跃游戏

贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

  1. var canJump = function(nums) {
  2.   if(nums.length===1) return true;
  3.   let cover=0;
  4.   for(let i=0;i<nums.length;i++){
  5.      cover=Math.max(i+nums[i],cover);
  6.      if(cover>=nums.length-1) return true;
  7.      if(cover===i)return false;
  8.   }
  9.   return false;
  10. };

45. 跳跃游戏 II

局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最小步数。

  1. var jump = function(nums) {
  2.   if(nums.length<2) return 0;
  3.   let count=0;
  4.   let curCover=0,nextCover=0;
  5.   for(let i=0;i<nums.length-1;i++){//i<nums.length-1，因为一定能到终点
  6.       nextCover=Math.max(i+nums[i],nextCover);
  7.       if(curCover===i){//走到实在没油了
  8.          curCover=nextCover//因为一定能到终点，续油
  9.          count++;
  10.       }
  11.   }
  12.   return count;
  13. };

452. 用最少数量的箭引爆气球

画图，找共同区间
局部最优：当气球出现重叠，一起射，所用弓箭最少。全局最优：把所有气球射爆所用弓箭最少。

  1. //更新重叠气球最小右边界
  2. var findMinArrowShots = function (points) {
  3.     points.sort((a, b) => {
  4.         return a[0] - b[0]
  5.     })
  6.     let result = 1;
  7.     for (let i = 1; i < points.length; i++) {
  8.         if (points[i][0] <= points[i - 1][1]) {
  9.             points[i][1] = Math.min(points[i - 1][1], points[i][1])//缩小右边界，尽可能一起射
  10.         } else {
  11.             result++;
  12.         }
  13.     }
  14.     return result;
  15. };
  17. //射一个，气球数组就remove一个元素
  18. var findMinArrowShots = function (points) {
  19.     let res = 0;
  20.     points.sort((a,b)=>{
  21.           if(a[0] !== b[0]){
  22.               return a[0]-b[0];
  23.           }else{
  24.               return a[1]-b[1];
  25.           }
  26.     })
  27.     while(points.length){
  28.         const tmp = points.pop()[0];
  29.         while(points.length && tmp <= points[points.length-1][1]){
  30.             points.pop();
  31.         }
  32.         res++;
  33.     }
  34.     return res;
  35. };

435. 无重叠区间

与用最少数量的箭引爆气球类似
为了保证区间不重合，移除数最少的情况下，即剩余数最多；
为了保证剩余数最多，在区间不重合的情况下，尽量让前面的右边界最小，因为前面占用越少，后面余量越多，数量就可能越多；
时间复杂度度：排序O(nlogn)，遍历O(n)，综合O(nlogn)
空间复杂度：O(logn)，为排序占用

  1. var eraseOverlapIntervals = function (intervals) {
  2.     intervals.sort((a, b) => {
  3.             return a[0] - b[0]
  4.     })
  5.     let result = 0;
  6.     for (let i = 1; i < intervals.length; i++) {
  7.         if (intervals[i][0] < intervals[i - 1][1]) {
  8.             intervals[i][1] = Math.min(intervals[i - 1][1], intervals[i][1])
  9.             result++;
  10.         }
  11.     }
  12.     return result;
  13. };

56. 合并区间

  1. //  按照左边界排序，排序之后局部最优：每次合并都取最大的右边界，这样就可以合并更多的区间了，整体最优：合并所有重叠的区间。
  2. var merge = function (intervals) {
  3.     let result = [];
  4.     intervals.sort((a, b) => a[0] - b[0]);
  5.     let pre = intervals[0]
  6.     for (let i = 1; i < intervals.length; i++) {
  7.         const cur = intervals[i];
  8.         if (cur[0] <= pre[1]) {
  9.             pre[1] = Math.max(cur[1], pre[1])
  10.         } else {
  11.             result.push(pre);
  12.             pre = cur
  13.         }
  14.     }
  15.     result.push(pre);
  16.     return result;
  17. };

763. 划分字母区间

利用该字母最后出现位置
其实这种方法不算贪心没有用到局部全局，可以得到字母出现的区间，然后使用合并区间。

  1. /**
  2.  * @param {string} s
  3.  * @return {number[]}
  4.  */
  5. var partitionLabels = function (s) {
  6.     let left = 0,
  7.         right = 0;
  8.     let result = [];
  9.     let map = Array(26).fill(0);
  10.     for (let i = 0; i < s.length; i++) {
  11.         map[s[i].charCodeAt() - 'a'.charCodeAt()] = i;
  12.     }
  13.     for (let i = 0; i < s.length; i++) {
  14.         right = Math.max(map[s[i].charCodeAt() - 'a'.charCodeAt()], right);
  15.         if (right === i) {
  16.             result.push(right - left + 1);
  17.             left = i + 1;
  18.         }
  19.     }
  20.     return result;
  21. };

股票问题

714. 买卖股票的最佳时机含手续费