Leetcode贪心算法

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

class Solution { public List partitionLabels(String s) { List 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 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,这时才能达到最大的状态。