Leetcode贪心算法

题目：划分字母区间  题号：763

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> list = new LinkedList();
        int[] edge = new int[27];
        char[] chars = s.toCharArray();
        for(int i = 0; i <chars.length;i++){
            edge[chars[i] - 'a'] = i; 
        }
        int left = -1;
        int right = 0;
        for(int i = 0; i < chars.length;i++){
            right = Math.max(right, edge[chars[i] - 'a']);
            if(right == i){
                list.add(i - left);
                left = right ;
            }
        }
        return list;
    }
}

首先创建一个结果集用来存放我们想要的结果。然后用for循环进行遍历数组，用每一个数字和a进行相减得到他们的阿斯克码值这个值对i进行赋值。取到一个最大的数，这个就是我们的右区间，然后再更新左区间，继续遍历。

题目：合并区间  题号：56

class Solution {
    public int[][] merge(int[][] intervals) {
        LinkedList<int[]> result = new LinkedList<>();
        Arrays.sort(intervals,(a,b) -> Integer.compare(a[0],b[0]));
        result.add(intervals[0]);

        for(int i = 1; i < intervals.length;i++){
            if(intervals[i][0] <= result.getLast()[1]){
               int start = result.getLast()[0]; //左区间
               int end = Math.max(intervals[i][1],result.getLast()[1]); //右区间
               result.removeLast();
               result.add(new int[]{start, end});
            }else{
                result.add(intervals[i]);
            }
        }
        return result.toArray(new int[result.size()][]);
    }
}

这道题目的核心是进行区间的比较和判断，需要将i的右区间和i-1的左区间进行比较，如果有重合的部分那就进行合并，在这里使用的是result取出最后一个元素，方便后续处理。如果没有重合部分，那就那就添加到我们的result中。

题目：单调递增的数字 题号：738

class Solution {
    public int monotoneIncreasingDigits(int n) {
        String s = String.valueOf(n);
        char[] arr = s.toCharArray();
        int flag = s.length();
        //从后遍历 利用flag进行标记
        for(int i = s.length() - 1; i > 0;i--){
            if(arr[i-1] > arr[i]){
                arr[i-1]--;
                flag = i;
            }
        }
        
        for(int i = flag;i < arr.length;i++){
            arr[i] = '9';
        }
        return Integer.parseInt(String.valueOf(arr));
    }
}

题目的核心是从后向左去遍历这个数字，当然在这之前需要将数组转换为字符数字。方便后续的遍。如果在遍历时发现前一期数字比后一个数字大的话就将他-1直到小于i位置的数字为止。然后标记flag，把flag后面的数字全部更新为9,这时才能达到最大的状态。