@data2world 如果你用 win 的话要重新考虑一下。 我有一个不常用的 win 主机。 接了几次使用体验不是很好，UI 总是看起来怪怪的， 不过这个应该是 4K 的问题而不是显示器本身的个性问题 。

@data2world 没问题吧。 我第一年因为用的是 macbook air 没有 retina，所以那时候基本就是用 dell 这个当主显示器. 现在笔记本换成了 rmbp 所以 dell 当成副显示器放在旁边竖着看网页和终端了。PPI 肯定是没 rmbp 自己的好， 色彩什么的也是， 不过我觉得打代码是完全够的了。

P2415Q 两年没毛病。

搞得玩的吧， 有点 brainstorm 到感觉， 把蔡依珊都包含进去了

@kingcos 想实现一个吗？ 其实感觉还是有市场的。

3L 比较靠谱。 现在还是有人不能接受新 mac 所以还在淘老 mac 的， 包括我自己。 直接稍微高价一点挂上去， 等有心人。 你这个配置确实很好。

好像没有在 ipad 上碰到过跟 mac 的三指翻译那样方便的功能的 app ；

强在对于人性的拷问，剧情其实还好

一觉醒来真的是...楼主你面的到底是什么公司啊, POJ 的题目都出.

@qwsqwa 这里的第二维是 max value， 因为步长是 1， 可不可以这样， 第二维长度直接定义为链表本身的长度，也就是说只循环链表本身包含的这些个离散值， 而不是一次-1 这样的搜索？

@qwsqwa 膜拜一下， 这个思路可以说是很犀利了

@fml notability 手画的

我始终认为找一条直线是一个坑, 我 9L 的论证已经证明.
而且 UIXX 的思路整体也是正确的. 按照他的思路, 在三维, 也就是链表长度是 3 的情况下, 三维空间里面可以脑补一下, 最近的这个点完全不一定在 x = y && y = z 这条直线上, 也就是认为最优的新链表里面所有的节点都相等不太合理.

i 代表 index, [i]代表这个 index 位置的节点.
我有一个尝试性的思路: 对于任意两个元素, 如果 i < j, 但是!([i] >= [j]), 那么定义(i, j)为一个反转.

我有一个尝试性的思路:
第一遍:
对于每一个 i, 找到 i 左边的最小值, 记录为 min[i]
记录 delta[i] = max (nums[i] - min[i], 0)
然后 sum delta[i] for i in range (N), 得到一个 delta1; 这一个对应于把所有的 i 作为右端点参与的反转进行纠正, 纠正方式是将 nums[i[向下拉;

第二遍:
对于每一个 i, 找到 i 右边的最大值, 记录为 max[i].
delta[i] = max (max[i] - nums[i], 0)
delta2 = sum delta[i] for i in range (N). 这个对应于把所有 i 作为左端点参与的反转进行纠正, 纠正的方式是将 nums[i]向上拉.

比较两个 delta, 哪个小就是最好的纠正方式.

https://i.imgur.com/IxRDEYh.png

这个只是一个抛砖引玉, 暂时没有办法证明这个思路.

@UIXX 你这个思路好像整体是对的， 虽然我没有接触过这方面的编程实践， 不知道这种 constraint 搜索问题最后实现起来是什么难度， 尤其是维度增加的情况下。 不知道楼主面试的是什么职位， 如果面试的是算法工程师或者机器学习方面的， 还是有可能最后就是想要这个答案的。

如果是普通软件开发的面试， 感觉可能想要的是更加特性的一个解法。

我也想问一下 OP， 这个题目给的是多少时间？ 感觉 LC 的 hard 级别了有点，当然也有可能是我没想到点子上

@LxExExl 那你怎么处理 1 2 3 呢？

i = 0, 变成 2 2 3
i = 1, 变成 2 3 3

没了。

我也同意这个应该是有一个可以简化问题的观察的， 但是不太好找； 而且真正面试的时候估计还是要证明自己的猜想的

@forthdim l2 的 delta 只要把 C 拉到 E 就行了， 只有 CE 这么大，AB 不需要改变；

@binux 如果一次只+1 的话, 这个算法的复杂度太高了, 只要让数组里面的数字之间的差值足够大, 最后的复杂度估计按照面试的标准很难接受.

找一个距离最近的线应该是不对的

https://i.imgur.com/1y2qBmx.png

比如这里 ABC 这个波. 比较 l1, 中间这条线, 和 l2, 也就是 BE 所在的线;

A 垂线交点假如是 F, 忘记标了;

l1: 对 ABC 的距离之和是 AF + DE + CD = AF + CE, 修改成 l1 对应的 delta 也是这个值;

l2: 对 ABC 的距离之和是: AF + DE + CD + DE = AF + CE + DE, 比 l1 大, 但是他的 delta 只有 CE, 比 l1 的小;