package top100.贪心算法;

import java.util.ArrayList;
import java.util.List;

public class TOP {
    //121. 买卖股票的最佳时机
    public int maxProfit(int[] prices) {
        int res = 0, min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < min) {
                min = prices[i];
            }
            res = Math.max(res, prices[i] - min);
        }
        return res;
    }

    //55. 跳跃游戏
    public boolean canJump(int[] nums) {
        if (nums == null || nums.length == 0) {
            return true;
        }
        int max = 0; //每个位置可达的最大索引
        for (int i = 0; i < nums.length ; i++) {
            if (max >= i) { //保证i可达
                max = Math.max(max, nums[i] + i);
            }
        }
        return max >= nums.length - 1; //最大索引超出最后一个字符索引，则可达
    }

    //45. 跳跃游戏 II
    //贪心算法：让每次跳到最远，则跳跃次数可以最小
    //计算当前位置可以跳跃的范围，从范围里面选取一个可以跳跃的最远位置作为下一个位置
    public int jump(int[] nums) {
        int res = 0;
        int n = nums.length;
        for (int i = 0; i < n - 1;) {
            //每次跳跃选取下个阶段可以跳跃的最远值
            int maxIndex = nums[i] + i; //下个阶段可以跳跃的最大范围
            //直接跳到最后了
            if (maxIndex >= n - 1) {
                res++;
                break;
            }
            //选择下个跳跃范围内可以跳跃到的最远值
            int max = nums[i + 1] + i + 1;//下个范围跳的最远距离
            int index = i + 1; //最大数对应的位置
            for (int j = i + 2; j <= maxIndex; j++) {
                if (nums[j] + j >= max) { //如果相等，取后面一个
                    max = nums[j] + j;
                    index = j; //每次在上次能跳到的范围（end）内选择一个能跳的最远的位置（也就是能跳到max_far位置的点）作为下次的起跳点 ！
                }
            }
            i = index; //跳跃到最大位置上
            res++;
        }
        return res;
    }

    //763. 划分字母区间
    //贪心算法：先根据当前字符，寻找其最大索引，在这个字串中，寻找每一个字符的最大索引，截取为一个字串
    public List<Integer> partitionLabels(String s) {
        List<Integer> res = new ArrayList<>();
        //用map记录每个字符的最大索引
        int[] map = new int[26];
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            map[chars[i] - 'a'] = i;
        }
        for (int i = 0; i < chars.length;) {
            //当前字母的最大索引
            int maxIndex = map[chars[i] - 'a'];
            //更新字串中的maxIndex
            for (int j = i + 1; j < maxIndex; j++) {
                int curMax = map[chars[j] - 'a'];
                maxIndex = Math.max(maxIndex, curMax);
            }
            //截取为字串
            res.add(maxIndex - i + 1);
            i = maxIndex + 1; //更新索引
        }
        return res;
    }
}