leetcode658+有序数组找出距离数字x最近的k个数字

在一个非递减数组中，找到判态距离目标值，桥氏最近的数组索引。

如 1 2 3 6 7 8 ，目标值为4

返回 2

思路：

可以理解为 先用二分法找到这个目标值，如果找不到，那么就找它应该插入的顺序，判断插入顺序两边的元素谁和目标值近。掘消源

//中级

public class Solution {

public List<Integer>findClosestElements(List<Integer>arr, int k, int x) {

int n = arr.size()

if (x <= arr.get(0)) {

return arr.subList(0, k)

} else if (arr.get(n - 1) <= x) {

return arr.subList(n - k, n)

} else {

int index = Collections.binarySearch(arr, x)

if (index <0)

index = -index - 1

int low = Math.max(0, index - k - 1), high = Math.min(arr.size() - 1, index + k - 1)

}

//高级

public List<Integer>findClosestElements(List<Integer>arr, int k, int x) {

Collections.sort(arr, (a,b) ->a == b ? a - b : Math.abs(a-x) - Math.abs(b-x))

arr = arr.subList(0, k)

Collections.sort(arr)

return arr

}

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

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

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

示例 1:

输入: [1,0,2]

输出: 5

解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例 2:

输入: [1,2,2]

输出: 4

解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。

第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

先看题目要求，

1.每个孩子至少分配到 1 个糖果。

2.相邻的孩子中，评分高的孩子必须获得更多的糖果。

总的糖果最少

总结我们所有可能会遇到的情况，总的解决方法就是首先保证1越多越好，能发一个最好，之后以相差1的情况发放。

每个孩子至少一个糖果，那么什么样的情况孩子会得到一个糖果呢？

当这个孩子i，ratings{i] >ratings[i-1]，且ratings{i] <ratings[i+1]，边界可以单独考虑，简而言之就是处于“低谷”，“波谷”，以数学上的话来说，是函数的极小值。除此之外呢？

还有一种情况，连续的相同的值，而且是有条件的，例如，[1，2，3，3，2，1]，这种情况两个3处是1吗，不是，[1，2，3，3，3，游散2，1]，这种情况呢？

实际上，判断是不是发一个，可以这样想，如果上升之后就下降，就不是了，如果停留了，那可能是。

还有便是，连续的变化的时候，就是单调递增和递减时，以初始值为1，公差为拆冲 1 的等差数列发放

具体考虑便是，当单调递增时，初始值为1，当前发放的糖果比前一个多一个，如果到达了波峰，最高点，有可能下一个值补是最大值，有神御氏可能还是。

当不是最大值，意味着走“下坡路”了，此时，我们需要知道当前下降趋势走到了哪？将走到的地方记做极小值，此处发放一个糖果，以1的等差数列逆推之前的发放糖果数

如果还是最大值，但下一个不是最大值，其实处理方法跟之前一样

但是下下一个值还是最大值呢，那么下一个最大值为1

以几个个例子来看：

[1,2,3,2,1] ==> [1,2,3,2,1]

[1,2,3,3,2,1] ==> [1,2,3,3,2,1]

[1,2,3,3,3,2,1] ==> [1,2,3,1,3,2,1]

[1,2,3,3,3,3,3,2,1] ==> [1,2,3,1,1,1,3,2,1]

首先用第一种方法，这种方法其实不是第一次用了，接雨水有一个方法和这个类似

使用两个vector<int>left,vector<int>right

一种从左到右记录“单调递增的序列”，实际是ratings的单调递增序列(从左到右)

另一种从右到左记录“单调递增的序列”，实际是ratings的单调递减序列(从左到右)

先举个例子：

ratings: [1,2,3,3,2,1,0,1,3,2,1]

left:[1,2,3,1,1,1,1,2,3,1,1]

right: [1,1,1,4,3,2,1,1,3,2,1]

汇总时，取两者的最大值就可以了

下面是程序：

这是提交结果：

由于提交有了一段时间，实际结果是，时间上还不错，但是空间上不佳

补：left[i]=1，这个地方似乎可以一开始给left赋初值。

接下来，我们使用另一种方法，不使用两个vector，边遍历边处理，过程稍微复杂了一点

具体过程和思路中基本一致，部分细节上有些差别，都在程序的注释里面了

下面是程序：

下面是系统结果：

空间上有明显改善。

---