1 题目 力扣 146. LRU 缓存 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类： LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。 void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。 2 解析 2.1 LRU算法设计 由于 put 和 get 方法的时间复杂度为 O(1)，我们可以总结出 cache 这个数据结构必要的条件： 🔴 cache 中的元素必须有时序，以区分最近使用的和久未使用的数据

【单调队列】主要是为了解决以下场景： 给你一个数组 window，已知其最值为 A，如果给 window 中添加⼀个数 B，那么比较一下 A 和 B 就可以立即算出新的最值；但如果要从 window 数组中减少一个数，就不能直接得到最值了，因为如果减少的这个数恰好是 A，就需要遍历 window 中的所有元素重新寻找新的最值。 可以使用 优先级队列 来动态寻找最值，通过创建一个大（小）顶堆，可以很快拿到最大（小）值。 但优先级队列无法满足标准队列结构【先进先出】的时间顺序，因为优先级队列底层利用二叉堆对元素进行动态排序，元素的出队顺序是元素的大小顺序，和入队的先后顺序完全没有关系。 而【单调队列】结构，既能够维护队列元素【先进先出】的时间顺序，又能够正确维护队列中所有元素的最值。 1 题目 力扣 239. 滑动窗口最大值 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 2 解析 2.1 搭建解题框架 🟧 普通队列的标准 API： 1 2 3 4 5 6 class Queue{ // enqueue 操作，在队尾加⼊元素 n void push(int n); // dequeue 操作，删除队头元素 void pop(); } 🟨 【单调队列】的 API：

1 单调栈模板 题目 输入一个数组 nums，请你返回⼀个等长的结果数组，结果数组中对应索引存储着下一个更大元素，如果没有更大的元素，就存 -1。 解析 🔴 把数组的元素想象成并列站立的人，元素大小想象成人的身高。这些人面对你站成一列。如果能够看到元素「2」，那么他后面可见的第一个人就是「2」的下⼀个更大元素，因为比「2」小的元素身高不够，都被「2」挡住了，第一个露出来的就是答案。 🟡 for 循环要从后往前扫描元素，因为我们借助的是栈的结构，倒着入栈，其实是正着出栈。 🟢 while 循环是把两个「高个子」元素之间的元素排除，因为他们的存在没有意义，前面挡着个「更高」的元素，所以他们不可能被作为后续进来的元素的下一个更大元素了。 🔵 这个算法的复杂度只有 O(n)。 总共有 n 个元素，每个元素都被 push 入栈了一次，而最多会被 pop一次，没有任何冗余操作。 图解： 代码实现： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 int[] nextGreaterElement(int[] nums) { int n = nums.length; // 存放答案的数组 int[] res = new int[n]; Stack<Integer> s = new Stack<>(); // 倒着往栈⾥放 for (int i = n - 1; i >= 0; i--) { // 判定个⼦⾼矮 while (!

1.1 判断有效括号串 题目 给定一个只包括 '('，')' 的字符串 s ，判断字符串是否有效。即每个右括号 ')' 的左边必须有⼀个左括号 '(' 和它匹配。 解析 用一个变量 left 记录 '(' 相对于 ')' 的数量，遇到 '(' 就 +1，遇到 ')' 就 -1。如果最后 left==0，则括号串有效，否则无效。并且，如果中间出现 left 数量为负，则说明有 ')' 出现在 '(' 之前，也为无效。 代码实现： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 bool isValid(string str) { // 待匹配的左括号数量 int left = 0; for (int i = 0; i < str.

1 递归反转整个链表 题目 力扣 206. 反转链表 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 示例： 1 2 输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1] 解析 图解： 代码实现： 1 2 3 4 5 6 7 8 9 10 public ListNode reverseList(ListNode head) { if(head==null || head.next==null){ return head; } ListNode last=reverseList(head.next); head.next.next=head; head.next=null; return last; } 2个注意点： 🟡 递归函数要有 base case，如果链表为空或者只有⼀个节点的时候，反转结果就是它自己。 1 2 3 if (head == null || head.next == null) { return head; } 🟢 当链表递归反转之后，新的头结点是 last，而之前的 head 变成了最后⼀个节点，别忘了链表的末尾要指向 null。

题目 力扣 870. 优势洗牌 给定两个大小相等的数组 nums1 和 nums2，nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。 返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。 解析 这道题类似于【田忌赛马】，只不过马的数量变多了，精髓在于【打得过就打，打不过就拿自己的垃圾和对方的精锐互换 】。我们先分析【田忌赛马】，考虑以下 3 点： 🟡 如果田忌的 1 号选手 < 齐王的 1 号选手，显然应该用田忌垫底的马送人头，降低对方的战斗力。 🟢 如果田忌的 1 号选手 < 齐王的 1 号选手，则应该直接让两者相比。 🟠 当出现第二种情况时，即 T1 > Q1 时，要不要节约战斗力，用 T2 对抗 Q1？ 答案是不需要。假设 T2 > Q1，那么不论换不换 T1，T1 和 T2 都能对抗所有的 Q，这种节约毫无意义。 根据以上思路，我们的策略是： 将齐王和田忌的马按照战斗力排序，然后按照排名一一对比。如果田忌的马能赢，那就比赛，如果赢不了，那就换个垫底的来送人头，保存实力。 结合已学过的双指针技巧，代码实现如下： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class Solution { public int[] advantageCount(int[] nums1, int[] nums2) { int n=nums1.

二分思维的精髓就是：通过已知信息尽可能多地收缩搜索空间，从而增加穷举效率，快速找到目标。 1 二分查找框架 1 2 3 4 5 6 7 8 9 10 11 12 13 14 int binarySearch(int[] nums, int target) { int left = 0, right = ...; while(...) { int mid = left + (right - left) / 2; if (nums[mid] == target) { ... } else if (nums[mid] < target) { left = ... } else if (nums[mid] > target) { right = ... } } return .

本文主要记录最难掌握的一类双指针技巧——滑动窗口算法。算法思路很简单，就是维护一个窗口，不断滑动，时间复杂度为 O(N)。大致逻辑如下： 1 2 3 4 5 6 7 8 9 10 11 int left = 0, right = 0; while (right < s.size()) { // 增⼤窗⼝ window.add(s[right]); right++; while (window needs shrink) { // 缩⼩窗⼝ window.remove(s[left]); left++; } } 滑动窗口算法的代码框架如下： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 /* 滑动窗⼝算法框架 */ void slidingWindow(string s) { unordered_map<char, int> window; int left = 0, right = 0; while (right < s.

在处理数组和链表相关问题时，双指针技巧是经常用到的，双指针技巧主要分为两类：左右指针和快慢指针。所谓左右指针，就是两个指针相向而行或者相背而行；而所谓快慢指针，就是两个指针同向而行。 1 快慢指针技巧 题目 力扣 26. 删除有序数组中的重复项 给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。 将最终结果插入 nums 的前 k 个位置后返回 k 。 不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 解析 我们让慢指针 slow 走在后面，快指针 fast 走在前面探路，找到⼀个不重复的元素就赋值给 slow 并让 slow 前进⼀步。 这样，就保证了 nums[0..slow] 都是无重复的元素，当 fast 指针遍历完整个数组 nums 后，nums[0..slow] 就是整个数组去重之后的结果。 代码实现： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public int removeDuplicates(int[] nums) { if(nums.

1 合并两个有序链表 题目 力扣 21. 合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例： 1 2 输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4] 解析 这题比较简单，直接用 while 循环每次比较 p1 和 p2 的大小，把较小的节点接到结果链表上，如图所示： 虚拟头节点技巧 通过虚拟头节点这个占位符，可以避免处理空指针的情况，降低代码的复杂性。 当你需要创造⼀条新链表的时候，可以使⽤虚拟头结点简化边界情况的处理。 最后通过 p.next = n1; 将剩余的节点全都复制过去，不需要使用 while 循环一条一条复制。 代码实现： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { // 虚拟头结点 ListNode p = new ListNode(), res = p; ListNode n1 = list1, n2 = list2; while(n1!

差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。 1 原理 题目 给出⼀个数组 nums，要求给区间 nums[2..6] 全部加 1，再给 nums[3..9] 全部减3，再给 nums[0..4] 全部加 2……N步操作后问，最后 nums 数组的值是什么？ 解析 常规思路： 用for循环都给 nums[i…j] 加上 val ，时间复杂度为 O(N)。由于对 nums 频繁修改，效率很低。 差分数组： 对 nums 数组构造⼀个 diff 差分数组，diff[i] 就是 nums[i] 和 nums[i-1] 之差。原理如图： 这样构造差分数组 diff，就可以快速进行区间增减的操作，如果你想对区间 nums[i..j] 的元素全部加 3，那么只需要让 diff[i] += 3，然后再让 diff[j+1] -= 3 即可。 只要花费 O(1) 的时间修改 diff 数组，就相当于给 nums 的整个区间做了修改。多次修改 diff，然后通过 diff 数组反推，即可得到 nums 修改后的结果。 代码实现如下： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 // 差分数组⼯具类 class Difference { // 差分数组 private int[] diff; /* 输⼊⼀个初始数组，区间操作将在这个数组上进⾏ */ public Difference(int[] nums) { assert nums.

前缀和主要适⽤的场景是原始数组不会被修改的情况下，频繁查询某个区间的累加和。 1 一维数组中的前缀和 题目 力扣 303. 区域和检索 - 数组不可变 给定一个整数数组 nums，计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right，实现 NumArray 类： NumArray(int[] nums) 使用数组 nums 初始化对象 int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] ) 示例： 1 2 3 4 5 6 7 8 9 10 11 输入： ["NumArray", "sumRange", "sumRange", "sumRange"] [[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]] 输出： [null, 1, -1, -3] 解释： NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]); numArray.