一.买卖股票的最佳时机
问题概述：
给定一个数组prices，它的第i个元素prices[i]表示一支给定股票第i天的价格。
你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回0。
思路：
我站在每天的角度去看，总是拿历史到现在最低的价格买入，我看看今天的价格卖出，是不是比之前的历史的都要赚，如果都要赚我就卖，如果不是，我就不卖。
代码：
class Solution { public int maxProfit(int[] prices) { int minprice=Integer.MAX_VALUE; int maxProfit=0; for(int price:prices){ minprice=Math.min(price,minprice); maxProfit=Math.max(maxProfit,price-minprice); } return maxProfit; } }二.跳跃游戏
问题概述：
给你一个非负整数数组nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回true；否则，返回false。
思路：
01234
23114
24348
第一个数最大能跳到索引2，那索引2之前的最大数为4，那他最大再变更为4，那4>=4已经含盖了最后个索引，所以为true.
01234
32104
33334
第一个数最大能跳到索引3，那索引3之前的最大数还是3，那他跳不到4.为false
那我们就从第一个数开始遍历，每次跳1格计算当前能跳到的最远位置，当遍历的数>当前最远位置，那就没法跳了，就返回false。如果当前跳到的最远位置已经大于等于最后个位置，所以已经具备了跳到最后的能力，直接返回false。
代码最后一个return true永远不会执行，但不写会编译错误。
代码：
class Solution { public boolean canJump(int[] nums) { int maxReach=0; int n=nums.length; for(int i=0;i<n;i++){ if(i>maxReach){ return false; } maxReach=Math.max(maxReach,nums[i]+i); if(maxReach>=n-1){ return true; } } return true; } }三.跳跃游戏II
问题概述：
上一题问能不能跳到最后，现在问的是能跳到最后，最少只要跳几次。（题目保证一定能跳到最后）
思路：
倒着推，从左往右找第一个能跳到最后那个索引位置记作pos1,step++。再以pos1为目标位置，从左到右找第一个能跳到pos1的下一个pos2，step++,依次类推有几个pos就是最少跳跃次数。
那可能你会有疑惑，有木有可能跳不到pos1呢，其实你可以结合上题，它是从第一个数开始遍历的，能到最后，那期间的那些数都是可以跳的，那题目保证了从0能跳到最后n,那0到n这个区间一定包括pos1,那pos1左边必有能到它的数，那有人问呢，那pos2呢，这不就是n取pos1嘛，那不也就跳的到嘛。
代码：
class Solution { public int jump(int[] nums) { int pos=nums.length-1; int step=0; while(pos>0){ for(int i=0;i<pos;i++){ if(nums[i]+i>=pos){ pos=i; step++; break; } } } return step; } }四.划分字母区间
问题概述：
给你一个字符串s。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串"ababcc"能够被分为["abab", "cc"]，但类似["aba", "bcc"]划分是非法的,因为b在两个字符串都出现了。
思路：
如果'a'出现的位置为2，8，10，那是不是包含'a'的片段一定得分割到10，那前面如果有'b',位置为3，11那是不是就又得切到11这个位置。
那我们就可以想到，先把每个字母最后的位置记录下来，一个一个位置切下去，看到哪才能断。
代码：
class Solution { public List<Integer> partitionLabels(String s) { List<Integer> res=new ArrayList<Integer>(); int start=0,end=0; int[] last=new int[26]; for(int i=0;i<s.length();i++){ last[s.charAt(i)-'a']=i; } for(int i=0;i<s.length();i++){ end=Math.max(end,last[s.charAt(i)-'a']); if(i==end){ res.add(end-start+1); start=i+1; } } return res; } }
