特性单调栈是一种特殊的栈数据结构，它满足元素的单调性（单调递增或单调递减）。与普通栈相比，单调栈在出栈时有一定的规则，使得出栈后栈中的元素仍然保持单调性。 单调栈主要有两个操作：入栈和出栈。入栈时，先判断栈顶元素是否符合单调性，如果不符合，则将其弹出，一直重复此过程直到符合单调性后再入栈；出栈时，弹出栈顶元素即可。 算法应用单调栈在算法中有许多应用，例如在求解 Next Greater El...

LeetCode No.146 LRU缓存机制 LRU（Least Recent Used）策略：优先淘汰最近最少使用的数据，常用于缓存淘汰机制，如Linux系统的内存淘汰、Redis的缓存淘汰等。 基于哈希表和双向链表实现LRU核心思路是，利用双向链表存储键值对，哈希表存储键在链表中对应的节点指针，如下图所示 这样的好处是使访问和更新操作时间复杂度都在O(1)。 PUT操作 判断哈希表中k...

动态规划的关键思想在于将问题转换成较小的子问题，然后根据子问题的结果总结出一个状态转移方程，最后得到整个问题的解 7.1 打家劫舍LeetCode No.198 问题描述：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非...

分治的思想为将大问题分解为子问题，子问题再分解为更小的子问题，直到不能再拆分，然后再合并子问题的结果，通常需要用到递归。关键是要找对如何拆解问题。 5.1 不同的二叉搜索树LeetCode No.95 问题描述：给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜索树 。 思路：根据二叉搜索树的特点，左子树的所有节点值均小于根节点，右子树的所有节点值均大于根节点，同时对于每一...

分治的思想为将大问题分解为子问题，子问题再分解为更小的子问题，直到不能再拆分，然后再合并子问题的结果，通常需要用到递归。关键是要找对如何拆解问题。 5.1 不同的二叉搜索树LeetCode No.95 问题描述：给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜索树 。 思路：根据二叉搜索树的特点，左子树的所有节点值均小于根节点，右子树的所有节点值均大于根节点，同时对于每一...

3.1 深度优先DFS 问题1：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。Input: “23”Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”] 思路：深度优先搜索，从根节点到每个叶子节点的所有路径即结果，深度为子串的长度...

二分查找是一种在有序列表中查找元素的高效方法，时间复杂度（logN），二分查找思路和时间都比较简单，但是实际问题中的细节不可忽视。 3.1 搜索插入位置LeetCode No.35 问题描述：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置，你可以假设数组中无重复元素。 思路：按照二分查找法，定义low，high两个指...

双指针通常用在有序数组，链表的数据结构上，根据题目条件移动对应的指针。比如判断子串、链表是否有环的问题。 1.1 最长子串LeetCode No.524 题目描述：给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串输入:s = “abpcpl...

6.1 栈6.1.1用两个栈实现一个队列LeetCode No.232 题目描述：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作（push、pop、peek、empty）： 思路： 两个栈一个栈做队头（出元素），另一个栈做队尾（入元素） 每次push只需要push到尾栈 pop时如果头栈为空则将尾栈全部“倒入”头栈，如果头栈不为空取出栈顶元素返回，否则返回失败（...

4.1 根据前序与中序序列构造二叉树LeetCode No.105 问题描述：根据一棵树的前序遍历与中序遍历构造二叉树。 思路：根据二叉树的前序和中序（或后序和中序）的序列可唯一构造一棵二叉树，必须要有中序。前序遍历的第一个为根节点，找到根节点在中序中的位置，中序左边的节点都是根节点的左子树，右边的同理，然后可以用递归的方式求解。 示例代码： type TreeNode struct &...