Allenlzcoder的博客

2种方法，都要理解掌握！最简单的基于HashSet的就不写在下面了，过于简单了。

【代码】【重点】【特例】31.下一个排列。

中间的指针则进行遍历，发现元素0则跟头指针交换元素，并各自加1，发现元素2则跟尾指针交换，尾指针减1。思路还是很清晰的，多指针，一头一尾分别用来放置0和2。

基于栈是最好的方案，代码简单，时间复杂度低；dp代码复杂，复杂度高。

基础解法，必须掌握！

【代码】【重点】【DP】139.单词拆分。

跟完全背包问题的解法一致！相同思路，对比记忆！

一模一样，只是细节稍有出入，对比记忆！

在遍历数组时，我们不访问最后一个元素，这是因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了。如果访问最后一个元素，在边界正好为最后一个位置的情况下，我们会增加一次「不必要的跳跃次数」，因此我们不必访问最后一个元素。在具体的实现中，我们维护当前能够到达的最大下标位置，记为边界。我们从左到右遍历数组，到达边界时，更新边界并将跳跃次数增加 1。贪心是最优解法，必须掌握！重点理解，看B站视频辅助！

最大的K个元素 => 小根堆（类似上窄下宽的梯形）最小的K个元素 => 大根堆（类似倒三角形）

【代码】【重点!!!】【堆】215.数组中的第K个最大元素。

【代码】【重点!!!】【单调栈】84.柱状图中最大矩形。

【代码】【重点!!!】【栈】394.字符串解码。

时间复杂度：O(logMin(m, n))，空间复杂度：O(1)。

【代码】【重点】【DP】322.零钱兑换。

二维DP，自底向上，参见《算法小抄》中的解释，更容易理解！

代码会啰嗦很多，所以还是法1好哇！

【代码】【DP】5.最长回文子串。

【代码】【DP】64.最小路径和。

【代码】【DP】62.不同路径。

必须掌握，O(N^2) + O(N)

如果只有正数，我们只需要考虑最大乘积f[i]；有负数，需要考虑与负数相乘的数，越小越好。所以d[i] 维护最小乘积。f[i]表示以i结尾的连续子数组的最大乘积，d[i]表示以i结尾的连续子数组的最小乘积。

【代码】【摩尔投票】169.多数元素。

【代码】【位运算】136.只出现1次的数字。

【代码】【DP】198.打家劫舍。

【代码】【DP】118.杨辉三角。

相当于计算斐波那契数列。

【代码】【重点】【贪心】55.跳跃游戏。

【代码】【DP】121.买卖股票的最佳时机。

【代码】【重点】【优先队列】295.数据流的中位数。

必须掌握算法，关于单调栈、单调队列和环形队列相关参见《算法小抄》相关内容。

【代码】【栈】155.最小栈。

【代码】【栈】20.有效的括号。

利用mid区分左右段。

根据mid来分段，此思路需要牢记！

注意：寻找完边界后，要判断两者是否合法！

【代码】74.搜索二维矩阵。

基础方法，必须掌握！

注意：使用ArrayList删除尾元素比LinkedList要快很多！主要优化回文串判断部分。

【代码】【回溯】【DFS】51.N皇后。