452. 用最少数量的箭引爆气球

题目说明

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 x``start，x``end， 且满足 xstart ≤ x ≤ x``end，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

解题思路

有两个维度左边界和右边界，如果同时考虑则会顾此失彼，因此可以考虑先对一个维度进行处理固定下来，再来处理另外一个维度。本题先对依据左边界对整个数组进行了排序固定，再对右边界进行处理

• 获取当前气球的右边界，用于和其他气球左边界进行比较。
• 如果该气球的右边界大于等于其他气球的左边界说明这两个气球存在重叠的部份。但需要去更新气球的右边界，重叠部份应该取两个气球的交集部份：rightbound = Math.min(rightbound, points[i][1]);理论上左边界也应该更新，但是左边界并不需要在后续比较中用到，所以不管。
• 当气球的右边界小于其他气球的右边界时，说明此前的气球是一个区间的，而这一个气球需要用一支新的箭去扎了，相当于一个新的重叠区间开始。更新需要的箭的数量，并更新右边界，重复这个过程直到结束。但需要注意的是，当到达最后一个区间的时候在循环中箭的数量不会再增加了，所以最终返回的结果应该加1。

435. 无重叠区间

题目说明

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

解题思路

思路1

该题可以反向理解为找出所有的有重叠区间，自然用所有区间减去最终重叠区间的数量即是需要移除的区间的数量。因为有左区间和右区间两个维度，所以要先固定下一个维度后对另一个维度进行处理。

• 首先对区间的左边界进行排序，然后不断用区间的右边界rightbound去和其他区间的左边界进行比较。如果rightbound大于左边界则说明他们有重叠部份，并更新他们rightbound：rightbound = Math.min(rightbound, intervals[i][1]);否则说明新的区间和之前的没有重叠部份，重叠区间的数量加1。最终返回intervals.length - count即可

思路2

正向去思考需要移除多少区间，即发生重叠的时候就记录下来。

• 首先对区间的左边界进行排序，然后不断用右边界rightbound去和其他区间的左边界进行比较。如果rightbound大于左边界说明有重叠的部份，更新他们的rightbound，并且重叠的数量+1。当不重叠的时候，说明后续的可以重新处理了，更新右边界即可。

763.划分字母区间

题目说明

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

示例：

输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。

提示：

• S的长度在[1, 500]之间。
• S只包含小写字母 'a' 到 'z' 。

解题思路

区间的意思是：在该区间出现过的字母，不会出现在后面的区间中。最大的区间当然包含所有的字母，但我们需要把字符串划分为尽可能多的区间，即找到该区间出现过的所有字母中最后一个字母出现的位置。

• 首先对字母出现的最后位置进行处理，对数组进行遍历之后不断更新字母出现的最后位置。理论上要用HashMap，但因为只有26个字母，所以用数组记录即可，令edge[str[i] - 'a'] = i。
• 再次对str进行遍历，通过获取出现的每个字母的最后位置，来不断更新片段的边界获取可能的末尾index = Math.max(index, edge[str[i] - 'a']);，同时用start记录片段的起始位置。当index和i相等的时候说明该片段的末尾已经找到了，将start和index记录下后更新到index + 1的位置。

56. 合并区间

题目说明

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

解题思路

和435. 无重叠区间或其他题的区别在于，此处是要用无重叠区间去囊括那些分别重叠的区间，不重叠的区间需要分到不同的无重叠区间中。因此，右边界rightbound不再是取小，不同区间不再是取交集，而是取并集，直到并集的右边界小于新区间的左边界即可。

• 首先对左边界进行排序，固定下这个维度后对右边界进行处理。
• 当rightbound > intervals[i][0]时，right = Math.max(right, intervals[i][1]);更新右边界取并集
• 当rightbound <= intervals[i][0]时，将leftbound（先前记录）和rightbound加入结果。当遍历结束之后，最后一个区间是还没有被加入结果的，要再加入一次后才是最终答案。

738.单调递增的数字

题目说明

给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）

示例 1:

• 输入: N = 10
• 输出: 9

示例 2:

• 输入: N = 1234
• 输出: 1234

示例 3:

• 输入: N = 332
• 输出: 299

解题思路

易知无论任何数字，如果出现递减的情况的话，肯定要把它处理成"xxx999"类似的形式。而这个xxx999的数字一定要比先前的数字要小，说明在9前面的x，必须比之前的要小。由此我们需要一个标志位来记录从何处开始输出9，自然要从后向前遍历来处理。

• 首先要对数字进行处理，因为涉及逐位比较，自然想到要用数组。此处可以先将数字n通过String.valueOf()的方法将其处理成字符串，再通过toCharArray()的方法将其转换成字符数组，便于后续的处理。
• 自后向前遍历。当chars[i] > char[i + 1]时则意味着出现了递减的情况，此时需要将flag位置更新为i + 1，同时为了保证更新的数字小于先前的数字，i处的位置要-1处理
• 当遍历完成后，对修改好的数组进行汇总。从flag到末尾全都是补9，flag之前的数组肯定是满足递增顺序的，直接加上即可

968.监控二叉树

题目说明

给定一个二叉树，我们在树的节点上安装摄像头。节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。计算监控树的所有节点所需的最小摄像头数量。

解题思路

易知二叉树的题目首先要通过遍历来完成，自然要考虑遍历方式。在此题中很明显是要么自顶向下处理要么自底向上，自底向上比较符合我们的预期（因为叶子节点如果放监控的话大概率会造成浪费，叶子会比较多），因此采用后序遍历。

可以判断每个节点只有三种状态：没有被监控、已经被监视、还未被监控，分别可以用0、1、2三个数字来判定，因此遍历方法的返回值不可以是空，需要用int来返回该节点的状态。由于自底向上我们可以获得left节点和right节点的状态，并依据此来判定当前节点应该怎样去处理及返回什么结果：

1. 当left和right有一个是监控的时候，当前节点就被监控了
2. 当left和right有一个没有被监控，则需要当前节点是监控去监控下面，监控数量+1
3. 当left和right都被监控时，当前节点也不需要做监控了，自然自身没有被监控

在处理叶子节点时，我们倾向于不让叶子节点不做监控（大概率会浪费），因此在返回空值时我们可以设定空节点被监控了，让叶子节点获得一个未被监控的返回值。

最后要额外注意一下根节点，根节点也是有返回值的！根节点也同样可能是三种状态中的一种，如果根节点没有被监控的话，则需要他自己去做一个监控来监控他自己，最终返回的监控数量要+1