刷题碎碎念，浅谈一下 leetcode hard

简单说明下po情况：

本想在刷满100题后写一个帖子，不过似乎找到了一个好的例子，于是就聊聊~


Po主刷题并不主要是为了找工作，还是因为有时间练练手。不过因为po主工作有一段时间了 (>15年), 也想聊下结合面试的。


一般来说，Leetcode medium挺适合作面试题，不过medium基本上对po主而言没什么难度，所以刷得少，就随便做做（也快100题了[facepalm]）。于是转战hard, 主要是随机选题，偶尔也刷刷高频，然后发现也不喜欢hard....
以po主模糊的记忆，最近碰到好几个hard:
1. 难度八分都在推公式，特别是组合公式，一旦公式完成，剩下就是一个简单的medium甚至easy...但是，有多少工作是要人推组合公式的？有那么几天连续做到这种题目，想吐..。
2. 还有一种hard，可能是真“hard”，就是算法知道，就是套用算法/数据结构 A, 然后算法/数据结构B...（连续两三个），然后这两三个都不是特别容易写，规定时间内写出来写对也不是特别容易（特别是对我这种工作15+年的）。可能用来面刚毕业的比较合理吧，或者面有竞赛背景的，看是不是蹭的名次。
3. 第三种我想重点吐槽，例子是这个 3430，这种题的特点：

• 有naive写法，通常不让过
• 有最优写法，candidate不一定能想出来，提示也不一定行
• 有次优写法，但是实现复杂度其实最复杂

简单说下这题：这题是要找一个数组中所有子数组（长度最大为k）的最大值和最小值，然后求和。
po主看了这题后，觉得，显然，n^3 的解法应该是不让过的。
po联想到一种求最长上升/下降子序列的解法，不想写（这时po主还不知道mono stack)
po主想了想，用平衡树或者线段树可以降到nlogn，但是python既没有现有的平衡树也没有现有的线段树，不想写。
po主还是写了个线段树，TLE.
po主觉得面试中自己碰到这样的题目估计也过不了了，于是看答案。
Mono stack的字眼进入po主眼睛，这玩意不难以理解，写法也比线段树简单很多，于是写了一下。
po主想说的是，这种特定的算法，要是一开始没有思路，其实面试官的hint很多时候是没有啥用的（po主自己面试人或者被面试都是这个感觉）。算法面试中想要不给答案但是又提供hint..这种hint基本等于没有。
所以这种题目考什么呢？我手搓一个线段树会比mono stack更高分吗？（况且还不一定能搓对）。
于是来吐槽..


po主刷得不算多，也没有去记，大概就这些了。


如果非要说有啥take away的话，就是: 推荐 hard 只刷高频或者list上的，不要刷随机的


还有啥想说的就是，新人求点米



补充内容 (2025-04-18 00:32 +08:00):

高亮一下，感谢 @Phenomenon.  提到一个叫“灵茶山艾府”的博主的题单，对考点做了分类。
这是他的github: https://github.com/EndlessCheng

Phenomenon. 发表于 2025-4-15 17:22
.1point3acres3430典型的贡献法+乘法原理呀，算是单调栈典型变种了。第一反应就应该是枚举子数组的最值，然后单调栈统计 ...

我以为毕业了之后，终于不用再羡慕为什么有的同学居然能讨论数学卷的最后一道题

做题这个事情确实需要一些天赋，好多专注度和思维方式，有的时候觉得不是单纯靠练习可以完成的

利益相关：leetcode 题  重复做，经常容易忘记 。。

starhder 发表于 2025-04-15 19:54:09
. Χ乘法原理那部分我倒是会推，所以难度不是这部分。

单调栈这种东西工作中还是以前竞赛都没用到，所以不知道..

这么常见的解题套路都不知道恰好说明了见的题不够多，这思想在leetcode出现了至少5-6次，在codeforces快被考烂了…类似的贡献法思想还有可能与前后缀分解，哈希表乘法原理统计，以及数据结构优化的线性DP结合起来考察。这些都是hard专属知识点哦。单调栈的另一种玩法是寻找next greater element，代表题是739。知识点有盲区很正常，但我觉得没必要给自己找一堆理由，让自己有侥幸的心态，这很不利于知识框架的构建。刷题就是为了查缺补漏的，心态上应该更多的是庆幸而不是抱怨。

面试向的刷题和竞赛向的刷题是两个概念，前者主要强调常用方法的熟练度，后者主要强调知识的广度。面试在于沟通和快速的类型匹配，解出题目，如果因为知识点缺漏造成发挥不好，只能说实力不过关，挂了也正常。平时训练的时候，我认为一定不要给自己设限，刻意区分“这东西面试不会考”…万一哪天面试官想考一考呢，岂不是有可能错失了机会很后悔？如果既有熟练度又有广度，准备面试向的算法题完全是放松神经，岂不美哉？我个人的爱好之一就是在刷题群里答疑算法题，市面上最难的snowflake oa我也没问题。况且现在市场这么不好，让自己各方面变得最强总归是没错的。

gary_mo 发表于 2025-04-16 16:49:24
请问楼主有没有推荐的刷题策略呢，大部分常考medium, hard 都刷过，但是做oa的时候还是有些时候会卡住，特别是对于runtime要求比较严的

推荐国区leetcode一个叫“灵茶山艾府”博主的题单，他的题单把所有常见的考点都做了分类，看完之后能应付98%以上leetcode的题目了

3430典型的贡献法+乘法原理呀，算是单调栈典型变种了。第一反应就应该是枚举子数组的最值，然后单调栈统计边界，然后用乘法计算每个数字作为max/min时，长度最长为k的子数组的数量，这里有点排列组合的思想，需要小心一点。类似题还有：907, 2818。如果反应不过来只能说刷题还没刷到位，有些典型模版还没有形成肌肉记忆，还需要总结并多加练习。

leetcode的hard题主要分为两类，第一类是考了一些高级数据结构/算法，纯粹是知识点难，例如线段树/树状数组/马拉车算法/欧拉回路/求割点与桥/求强连通分支/字符串随机哈希/中国剩余定理/矩阵快速幂优化/埃氏筛质数/gcd及其倍增之类的，这种题完全考验知识的广度。还有一类是超过3道medium难度的题目缝合而成的hard，这类题一般不会很难，但是很考验基础知识的扎实程度，我很喜欢这类题目，做一道相当于复习了4-5个知识点。

利益相关：leetcode题量1362，竞赛分2204

Phenomenon. 发表于 2025-4-15 17:22
3430典型的贡献法+乘法原理呀，算是单调栈典型变种了。第一反应就应该是枚举子数组的最值，然后单调栈统计 ...

乘法原理那部分我倒是会推，所以难度不是这部分。

单调栈这种东西工作中还是以前竞赛都没用到，所以不知道..

另外高级数据结构，算法，在面试或者工作中都没啥太大意义，除非考察专门搞这种的。。。

总的来说我几部推荐面也不推荐刷（主要针对工作有一定年限的）。。

什么都不会，老年人，怎么刷题

首先膜拜一下大神，感谢分享，非常有用。

但面试官都是看人下菜，真的给一道这种题就是不想让过，你就是图灵再世，bug free写出来，又怎么样？ hm也可以以各种借口pass简历，不给strong hire。

我老婆公司it部门全是某特定族裔， 有职位放出来，非常outdated的技术栈，关键词咱可以全match，我有某大厂云服务背景，老婆找个认识的三哥ic打探，人家好心相劝，我们部门领导很可能只招印度人，我帮你推但你们别报期望😭

看来leetcode hard已经不能满足大家的刷题需求了。建议再出比hard更高一级的难题，命名为nightmare。

han6 发表于 2025-4-16 14:32
看来leetcode hard已经不能满足大家的刷题需求了。建议再出比hard更高一级的难题，命名为nightmare。

这个不太需要呀，有各种竞赛题库...
为了面试的话其实没太大必要...

han6 发表于 2025-04-16 14:32:14
看来leetcode hard已经不能满足大家的刷题需求了。建议再出比hard更高一级的难题，命名为nightmare。

现在周赛的最后一题已经能达到你说的难度要求了。普通hard难度分大概在1900-2300之间，现在周赛的最后一题难度分大概在2900-3100之间，等价于codeforces 2200左右=NOIP省选中难题=ICPC区域赛中等题，足够nightmare了吧。面试如果遇到了基本等于劝退