134. 加油站

题目说明

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

说明:

• 如果题目有解，该答案即为唯一答案。
• 输入数组均为非空数组，且长度相同。
• 输入数组中的元素均为非负数。

解题思路

• 如果gas总和大于cost总和的话（即rest总和大于等于 0 ），说明该题一定是有解的，只需要去考虑起点即可。通过贪心的方法去判定起点：当curSum < 0 时说明从之前的起点到当前位置会出现开不到的情况，说明起点需要更新，至少从下一个位置开始重新尝试
• 当遍历结束时，去判定rest是否大于等于 0 即可，大于的话则返回求出的起点（用start记录），否则返回 -1

135. 分发糖果

题目说明

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
• 相邻的孩子中，评分高的孩子必须获得更多的糖果。

那么这样下来，老师至少需要准备多少颗糖果呢？

解题思路

该题可以理解为要从两个维度去看问题，一个是和左边比较，一个是和右边比较。但是无法同时兼顾两个维度，否则需要同时去更新多个值且还可能还需要回过头去修改已经设定好的值。因此可以将维度拆开来看，最后进行汇总。

• 首先从左往右遍历，如果大于左边的值则加一，不然将当前糖果数量置为1即可（每个小孩至少要获得一个糖果）
• 然后再从右往左遍历，因为此时每个位置都有分配一个糖果了且这个糖果的数量从左往右看是合法的，因此我们只需要和右边比较即可。获得了新的值后两者取max（同时满足左右的要求），判断逻辑和从左向右遍历相同
• 左右都遍历完后即获得每个小孩获得的糖果数量，求和即获得最终答案

406.根据身高重建队列

题目说明

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

示例 1：

• 输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
• 输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
• 解释：
  • 编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
  • 编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
  • 编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
  • 编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
  • 编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
  • 编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
  • 因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

解题思路

本题同样可以理解为两个维度，一个是身高维度hi，一个是前面同学数量的维度ki。如果同时考虑两个维度的话，可能会导致对已经放好的同学进行位置的调整，所以将其转换为两个维度分别处理的问题。

接下来要决定先处理哪一个维度。如果先处理前面同学数量的维度，则将同学按照ki从小到大进行排序，但身高这个时候不知道应该怎么处理。因此决定先对身高从大到小排序，当身高相同时则根据ki从小到大排序（就比如(7,0)和(7,1)，一定是ki = 1的在后面）

• 对身高排序，重写sort方法（从小到大则前者减后者，反之后者减前者）

  Arrays.sort(people, (a, b) -> {
              if (a[0] == b[0]) {
                  return a[1] - b[1]; // 身高相同时第二个维度从小到大
              }
              return b[0] - a[0]; // 第一个维度从大到小
          });
  

• 身高排序要之后开始处理ki，此处涉及一个技巧linkedList.add(person[1], person);因为身高已经是从大到小排序的了，则从ki位置插入可以把之前当前位置后续的往后推，这并不会影响后面的合法性（当新插入的比较矮时不影响，当新插入的身高和前一个插入的相同时则排在它的后面）