代码随想录刷题day31丨56. 合并区间，738.单调递增的数字，总结

代码随想录刷题day31丨56. 合并区间，738.单调递增的数字，总结

1.题目

1.1合并区间

• 题目链接：56. 合并区间 - 力扣（LeetCode）

  

• 视频讲解：贪心算法，合并区间有细节！LeetCode：56.合并区间_哔哩哔哩_bilibili

• 文档讲解：https://programmercarl.com/0056.%E5%90%88%E5%B9%B6%E5%8C%BA%E9%97%B4.html

• 解题思路：贪心

  • 判断区间重贴后要进行区间合并。
  • 先排序，让所有的相邻区间尽可能的重叠在一起，按左边界
  • 按照左边界从小到大排序之后，如果 intervals[i][0] <= intervals[i - 1][1] 即intervals[i]的左边界 <= intervals[i - 1]的右边界，则一定有重叠。（本题相邻区间也算重贴，所以是<=）
  • 知道如何判断重复之后，剩下的就是合并了，如何去模拟合并区间呢？
    • 其实就是用合并区间后左边界和右边界，作为一个新的区间，加入到result数组里就可以了。如果没有合并就把原区间加入到result数组。

• 代码：

  //时间复杂度: O(nlogn)
  //空间复杂度: O(logn)
  class Solution {public int[][] merge(int[][] intervals) {//按照左边界排序Arrays.sort(intervals,(a,b) -> Integer.compare(a[0],b[0]));List<int[]> result = new LinkedList<>();// 第一个区间就可以放进结果集里，后面如果重叠，在result上直接合并result.add(intervals[0]);for(int i = 1;i < intervals.length;i++){if(intervals[i][0] <= result.getLast()[1]){result.getLast()[1] = Math.max(intervals[i][1],result.getLast()[1]);}else{result.add(intervals[i]);}}return result.toArray(new int[result.size()][]);}
  }
  

• 总结：

  • 本质其实还是判断重叠区间问题。

1.2单调递增的数字

• 题目链接：738. 单调递增的数字 - 力扣（LeetCode）

  

• 视频讲解：贪心算法，思路不难想，但代码不好写！LeetCode:738.单调自增的数字_哔哩哔哩_bilibili

• 文档讲解：https://programmercarl.com/0738.%E5%8D%95%E8%B0%83%E9%80%92%E5%A2%9E%E7%9A%84%E6%95%B0%E5%AD%97.html

• 解题思路：贪心

  • 从后往前遍历
  • 一旦出现chars[i - 1] > chars[i]的情况（非单调递增），首先想让chars[i - 1]减一，chars[i]赋值9

• 代码：

  class Solution {public int monotoneIncreasingDigits(int n) {String s = String.valueOf(n);char[] chars = s.toCharArray();// flag用来标记赋值9从哪里开始// 设置为这个默认值，为了防止第二个for循环在flag没有被赋值的情况下执行int flag = chars.length;for(int i = chars.length - 1;i > 0;i--){if(chars[i - 1] > chars[i]){chars[i - 1]--;flag = i;}}for(int i = flag;i < chars.length;i++){chars[i] = '9';}return Integer.parseInt(String.valueOf(chars));}
  }
  

• 总结：

  • 最后代码实现的时候，也需要一些技巧，例如用一个flag来标记从哪里开始赋值9。

2.贪心总结

• 贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

• 贪心没套路，就刷题而言，如果感觉好像局部最优可以推出全局最优，然后想不到反例，那就试一试贪心吧！

• for循环适合模拟从头到尾的遍历，而while循环适合模拟环形遍历