贪心算法+leetcode原题

定义：一种在每一步选择中都采取当前状态下最好或最优（即最有利）的选择，从而希望导致全局最优解的算法策略。

example1 leetcode 跳跃游戏55

给你一个非负整数数组 nums ，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
- 示例 1：
  输入：nums = [2,3,1,1,4]
  输出：true
  解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int length=nums.size();//数组长度
        int arlength=0;//能到达的最大坐标，初始只能到达0
        for(int i=0;i<length;i++)
        {
            if(i<=arlength)//i<arlength，说明我可以到达i，
            arlength=max(i+nums[i],arlength);//比较a[i]+i这个新的可以达到的长度是不是可以超过最大长度，超过则更新最远可以到达的长度
            if(arlength>=length-1)//大于或等于数组长度
            return true;
        }
        return false;
    }
};

example2(贪心策略双指针) leetcode 承最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
2.代码

public:
    int maxArea(vector<int>& height) {
        int lenx=height.size();
        if(lenx==0&&lenx==1)
        return 0;
        int maxsize=0;
        int i=0,j=lenx-1;
        while(i<j)
        {
             maxsize=max(min(height[i],height[j])*(j-i),maxsize); 
             if(height[i]>=height[j])
             j--;
             else
             i++;
        }
       return maxsize;
    }
};