我的经验就是，如果是原题高频题，电面中最好会牛逼解法，因为他们喜欢问一些比较tricky的原题，而你只要写过了就行。但是onsite时，经常会遇到没有原题的情况，一般不需要你有最tricky最牛逼的解法。公司需要的是考量你能否准确把握问题并提供跟tricky解同量级的(big O)解答思路，个别公司还很强调bug free。如果你灵光乍现想出个tricky解法，花了挺长时间让面试官认可，虽然会让面试官惊喜，但是某些情况下对你整体帮助并不会很大。

几个公司onsite你可以比较下：

F: 题目集中在medium到初等hard，medium居多，要求bug free，原题数量偏低，题目思路比较清晰，tricky解法很不常见。（如果有system design，那么design做的好远比写出tricky解法加分多）

L: 题目集中在medium到初等hard，medium到hard参半，最好bug free，原题偏多，题目思路比较清晰，tricky解法很不常见。（如果有system design，和过去project展示，那么design和展示做的好远比写出tricky解法加分多）

A: 题目集中在medium，最好bug free，原题偏多，思路比较清晰，tricky解法很不常见。（更看重OOD，system design，以及比重最高的behavior question）

G: 题目集中的medium到最难的hard，hard题居多，原题极少，偏medium的题要写好code，hard的题很多时候不要求写代码，或者不需要写完代码，思路需要通过思考得出，最容易出现多解法，最容易存在tricky解，tricky解加分很多，因为这种情况下tricky解经常代表你比别人更加看清楚了这个题的本质（system design越高级越重，5级前不面design）

上面分析是我之前的经历的感觉，不具备典型代表性，只为了说明下问题。你看，这几个公司里，真正比较有空间让你搞tricky解得，也就G，但是G又不是原题，能临场想出个比较优秀的时间空间复杂度解，拿offer已经足够了。leetcode上的tricky解，欣赏欣赏就可以了，主流的大思路要掌握。等你足够牛逼了你再自己创造去。

当年phone interview面过这道题，直接用你链接里面的方法解的，然而面试官表示第一次见这么惊奇的做法，跟他解释了好久，各种证明，最后过了。但如果再来一次的话，我可能先用常规解，再看面试官要不要求优化。

ps后来onsite的时候又遇到了给我出这题的面试官（因为是组面），出了道least used cache，结果要我一直优化，做出最优最优解。。。综上，一道题从普通解到最优解/lc上的奇异解，最好都掌握吧。另外这家是很不错的公司，但并不是FLAG。

单从楼主给的那道题来看，我建议还是要掌握最优解，原因是这道题最优解的思路可以应用到很多别的hard题目中去，比如skyline problem中就会应用到这种排序的思想

其次要不要追求最优解主要看你刷了多少题，我个人的见解是一开始应该追求广度，尽量多做题，十分钟想不出来就去看答案都行，一定要扩展自己的“见识”。

之后当给你一道新题，你能大概判断出来这是什么类型的题，可能的思考方向有哪些之后就应该开始注重是否能优化了

最后应该能做到把见过的题分门别类，在心里面创建一个目录，把思维方式归类

其次，我建议楼主不要死记最优解，看最优解的目的是能够构建起一条完整的逻辑链条把解体过程串起来帮助自己思维，大概类似于：

这道题的核心是需要得到A，所以我应该需要B；为了得到B，我可能需要C和D；为了得到C和D我需要设计一系列的策略，大概是。。。最终我归纳出来的解体思路是XXXX

另外补充一个小trick，其实题目的数据范围是个很有用的hint：

n>100k: 要求 O(nlogn) 到 O(n)，通常就是二分，heap，线段树，贪心，dp+优化，记忆化search

n>10k：和上面差不多，偶尔见到O(n sqrt(n))，或bfs之类

>1k：基本就是O(n^2)，dp之类的也很常见

>100：常见非常暴力O(n^3)，且很容易出难题，得想办法优化才能O(n^3)或dfs

>10：通常是状态dp O(2^n)，或者O(n^4)的暴力题

最后还有不给范围的，通常O(n)到O(nlogn)比较靠谱

实话实说，题目做的越多必然越强（对比以前的自己）。个人感觉50题是第一个坎，做了50题就开始有感觉了。200题是第二个坎，200题后思路就打开了，能做的题目范围大幅提高。直到500之前一直处于平台期，感觉没有明显提高，然后500题后会发现对代码的感悟已经完全不一样了，出思路的时间明显缩短，以前觉得很复杂很绕的题目似乎游刃有余。再后面的坎我还没遇到，500到1000题这个段我只是感觉能力在慢慢提高，代码越写越短，手速也越来越快。

我觉得大家面算法的时候一定要跟面试官解释清楚，确定面试官理解了再写，否则时间就白白浪费了。解释dp的时候还是先从比较直接的方法开始比较好，如果有需要再慢慢优化，一上来就给最优解有时确实不太好理解。