Posts

LeetCode 42 https://leetcode.cn/problems/trapping-rain-water/description/ 难度：困难 本题为常考的 Hard 题目，有多种做法，分别是前后缀分解，相向双指针和单调栈。本文使用单调栈方法。单调栈的做法相当于「横着」计算面积。 这个方法可以总结成 16 个字：找上一个更大元素，在找的过程中填坑。 如果当前元素大于栈顶元素，栈顶元素作为底边，当前元素作为右边，再找栈中第二小的元素作为左边。这段区域可以接的水为 min(height[left], height[i]) - bottom_h * (i - left - 1)。如果找不到第二小的元素，说明这一段不能接水。最后将 i 入栈。 时间复杂度：O(n)，其中 n 为 height 的长度。虽然我们写了个二重循环，但站在每个元素的视角看，这个元素在二重循环中最多入栈出栈各一次，因此循环次数之和是 O(n)，所以时间复杂度是 O(n)。 空间复杂度：O(min(n,U))，其中 U=max(height)−min(height)+1。注意栈中没有重复元素，在 height 值域很小的情况下，空间复杂度主要取决于 height 的值域范围。 ...

LeetCode 160 https://leetcode.cn/problems/intersection-of-two-linked-lists/description/ 难度：简单 最简单的方法是使用哈希集合来记录访问过的节点。除此之外还有双指针的做法。 我来到你的城市，走过你来时的路。 初始化两个指针 p = headA, q = headB。 不断循环，直到 p == q。 每次循环，p 和 q 各向后走一步。具体来说，如果 p 不是空节点，那么更新 p 为 p->next，否则更新 p 为 headB；如果 q 不是空节点，那么更新 q 为 q->next，否则更新 q 为 headA。 循环结束时，如果两条链表相交，那么此时 p 和 q 都在相交的起始节点处，返回 p；如果两条链表不相交，那么 p 和 q 都走到空节点，所以也可以返回 p，即空节点。 时间复杂度：O(m+n)，其中 m 是第一条链表的长度，n 是第二条链表的长度。除了交点，每个节点会被指针 p 访问至多一次，每个节点会被指针 q 访问至多一次。 空间复杂度：O(1)。 ...

LeetCode 56 https://leetcode.cn/problems/merge-intervals/description/ 难度：中等 首先将数组按照左端点进行排序，然后如果当前区间左端点 <= 答案中最后一个合并区间的右端点，更新答案区间右端点为两者较大值；反之将当前区间加入答案。 时间复杂度：O(nlogn)，其中 n 是 intervals 的长度。瓶颈在排序上。 空间复杂度：O(1)。排序的栈开销和返回值不计入。 ...

LeetCode 415 https://leetcode.cn/problems/add-strings/description/ 难度：简单 本题为高精度加法。使用两个指针倒序遍历 num1 和 num2，最后处理有进位的情况。将 ans 反转后就是答案。 时间复杂度：O(max(m, n))。 空间复杂度：O(1)。 ...

LeetCode 143 https://leetcode.cn/problems/reorder-list/description/ 难度：中等 这道题目需要先找到链表的中间节点 LeetCode 876，然后反转后半部分的链表 LeetCode 206。 head 指向前半部分头节点，head2 指向后半部分的头节点。每次更新 head->next = head2, head2->next = nxt。 时间复杂度：O(n)，其中 n 为链表的长度。 空间复杂度：O(1)，仅用到若干额外变量。 ...

LeetCode 23 https://leetcode.cn/problems/merge-k-sorted-lists/description/ 难度：困难 本题是最小堆的题目。首先将 k 个链表的头节点加入堆，每次在链表中插入堆顶元素，再把堆顶元素的下一个元素入堆。 需要注意的是最小堆的声明方式。a > b（greater）是最小堆，a < b（less） 是最大堆。STL 的优先队列默认是最大堆。 auto cmp = [](const ListNode* a, const ListNode* b) { return a->val > b->val; }; priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq; 时间复杂度：O(Llogm)，其中 m 为 lists 的长度，L 为所有链表的长度之和。 空间复杂度：O(m)。堆中至多有 m 个元素。 ...

LeetCode 300 https://leetcode.cn/problems/longest-increasing-subsequence/description/ 难度：中等 本题求最长上升子序列（LIS）有两种做法，分别是动态规划和贪心。 ...

LeetCode 54 https://leetcode.cn/problems/spiral-matrix/description/ 难度：中等 对于已经访问过的数据，更改值为 INF，对其进行标记。定义方向数组，当访问到不合法的节点时，右转 90°，即 di = (di + 1) % 4。 时间复杂度：O(mn)，其中 m 和 n 分别为 matrix 的行数和列数。 空间复杂度：O(1)。返回值不计入。 ...

LeetCode 141 https://leetcode.cn/problems/linked-list-cycle/description/ 难度：简单 这道题目的做法是快慢指针。快指针每次走两步，慢指针每次走一步，如果快慢指针相等，说明链表有环。 时间复杂度：O(n)，其中 n 为链表的长度。 空间复杂度：O(1)，仅用到若干额外变量。 ...

LeetCode 92 https://leetcode.cn/problems/reverse-linked-list-ii/description/ 难度：中等 这道题需要翻转中间一段链表。我们定义这段链表的前一个节点为 p0。翻转结束之后，需要修改 p0->next->next = cur, p0->next = pre。 时间复杂度：O(right)。 空间复杂度：O(1)。 ...