文章目录
739. 每日温度
题目链接
标签
栈 数组 单调栈
思路
本题求解的是:对于第 i
天,下一个更高温度出现在几天后。抽象一下,就是 求 每个元素之后的更大元素的索引 与 当前元素索引 之差。
可以使用 单调栈 的思想解决,维护一个 从栈顶到栈底 温度 单调递增 的栈,这个栈存储未找到等待天数的天的索引。
遍历温度数组,对于第 i
天的温度 temp
,如果 栈中有索引 prevIndex
(这个索引取自 栈顶,是整个栈中温度最小的天的索引) 并且 该索引指向的温度比 temp
小,则 第 prevIndex
天的下一个更高温度出现在 i - prevIndex
天之后,它找到了自己的等待天数,可以将其移出栈中。重复这步操作,直到 没有未找到等待天数的天(栈中有索引) 或 第 prevIndex
天的温度比 temp
高。
可以发现:在栈中,越靠近栈顶,索引指向的温度越低;越靠近栈底,索引指向的温度越高。这就是 单调栈,它能解决 求每个元素之后的更大元素 的问题,稍微变形就变成了本题。
代码
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int len = temperatures.length;
int[] res = new int[len];
LinkedList<Integer> stack = new LinkedList<>(); // 存储 未找到等待天数 的天的索引
for (int i = 0; i < len; i++) {
int temp = temperatures[i]; // 获取第 i 天的温度
// 给 未找到等待天数 的每天 赋 等待天数 的值
// 直到 没有未找到等待天数的天的索引 或 之前有一天温度更高
while (!stack.isEmpty() && temp > temperatures[stack.peek()]) {
int prevIndex = stack.pop(); // 取出 未找到等待天数 的天数
res[prevIndex] = i - prevIndex; // 保存等待天数
}
stack.push(i); // 将 i 放到栈中,为它寻找更高温度
}
return res;
}
}
82. 删除排序链表中的重复元素 II
题目链接
标签
链表 双指针
思路
本题是去除链表中重复的所有元素,本质上是 删除节点,删除一个节点就是 让前一个节点指向后一个节点,跳过这个节点。发现这里使用到了 前一个节点,所以使用 哨兵节点 指向链表,避免 对删除第一个节点 进行的特殊处理。
要删除多个重复节点,除了原有的 前一个节点的指针 prev
和 这个节点的指针 curr
之外,还得使用一个指针 after
,after
指向不与 curr
重复的节点,最后得让 prev
指向 after
,从而删除 从 prev
到 after
之间的多个重复节点。
如果没有遇到重复节点,就让 prev
正常向右移动,并更新 curr, after
。
代码
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode sentinel = new ListNode(0, head); // 哨兵节点,指向原始链表
ListNode prev = sentinel; // 指向待检查节点,是它的前一个节点
ListNode curr; // curr 是待检查节点
ListNode after; // after 是待检查节点的下一个节点,它最终指向不与 curr 重复的节点
// 给 curr, after 赋值,并在它两个中有一个为 null 时退出循环
while ((curr = prev.next) != null && (after = curr.next) != null) {
if (curr.val != after.val) { // 如果 after 不与 after 重复
prev = prev.next; // 则让 prev 正常向右移动
continue;
}
// 找到不与 curr 重复的节点,null 也算不与 curr 重复
while ((after = after.next) != null && after.val == curr.val) {
continue;
}
prev.next = after; // 让 prev 指向这个节点
}
return sentinel.next; // 返回哨兵节点指向的链表
}
}
106. 从中序与后序遍历序列构造二叉树
题目链接
标签
树 数组 哈希表 分治 二叉树
思路
本题和 105. 从前序与中序遍历序列构造二叉树 十分相似,不过本题考查的是 中序遍历 和 后序遍历。
二叉树的三种遍历
先讲一讲二叉树的三种 (深度优先搜索) 遍历:
- 前序遍历:先处理本节点的值,再遍历左子树,最后遍历右子树。
- 中序遍历:先遍历左子树,再处理本节点的值,最后遍历右子树。
- 后序遍历:先遍历左子树,再遍历右子树,最后处理本节点的值。
例如对于下图:
它的三种遍历结果分别如下:
- 前序遍历:
[4, 2, 1, 3, 6, 5, 7]
。
可以这样分:[4], [2, 1, 3], [6, 5, 7]
,分别为:本节点、左子树、右子树。
左子树有三个节点的原因是:中序遍历的本节点[4]
前有 3 个元素。 - 中序遍历:
[1, 2, 3, 4, 5, 6, 7]
。
可以这样分:[1, 2, 3], [4], [5, 6, 7]
,分别为:左子树、本节点、右子树。
本节点为[4]
的原因是:前序遍历的第一个元素是4
或 后序遍历的最后一个元素是4
。 - 后序遍历:
[1, 3, 2, 5, 7, 6, 4]
。
可以这样分:[1, 3, 2], [5, 7, 6], [4]
,分别为:左子树、右子树、本节点。
左子树有三个节点的原因是:中序遍历的本节点[4]
前有 3 个元素。
由此可见:只要有中序遍历,再加上前序遍历或后序遍历的其中一种,就可以构建一颗二叉树。
值与索引的映射
在构建二叉树时,获取后序遍历的某一个值作为根节点,然后要根据这个值将中序遍历的结果划分成两部分,为了方便划分,可以使用一个 Map
来存储中序遍历的 值 与 索引 的映射。
对于后序遍历的使用
仔细观察后序遍历的结果 [1, 3, 2, 5, 7, 6, 4]
,可以发现一个很奇妙的东西:从后到前,4
是根节点,6
是右子树的根节点,7, 5
是右子树的两个子节点(也算是两个 null
的根节点),2
是左子树的根节点,3, 1
是左子树的两个子节点(也算是两个 null
的根节点)。
在使用递归的前提下,如果 先构建右子树,再构建左子树,最后返回本次构建的树,就可以把 倒序遍历 postorder
的结果 作为每棵树(或子树)的根节点。
对于中序遍历的使用
在区间 [inLeft, inRight]
上构建二叉树时,先通过后序遍历找根节点的值 rootVal
,然后通过 Map
寻找这个值在中序遍历中对应的索引 index
,接着进行划分:在区间 [index + 1, inRight]
上构建右子树,在区间 [inLeft, index - 1]
上构建左子树。最后将本次在区间 [inLeft, inRight]
上构建的二叉树返回。
代码
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
// 初始化成员变量
this.inorder = inorder;
this.postorder = postorder;
this.postIndex = postorder.length - 1;
for (int i = 0; i < inorder.length; i++) { // 构建中序遍历的 值 与 索引 的映射
this.indcies.put(inorder[i], i);
}
return build(0, inorder.length - 1);
}
private int postIndex; // postorder 数组的索引,指向正在构建的树的根节点
private int[] inorder; // 中序遍历数组
private int[] postorder; // 后序遍历数组
// 中序遍历的 值 与 索引 的映射,key 为 值,value 为 值在中序遍历数组中的索引
private Map<Integer, Integer> indcies = new HashMap<>();
// 在中序遍历数组的 [inLeft, inRight] 区间内,构建树
private TreeNode build(int inLeft, int inRight) {
if (inLeft > inRight) { // 如果区间内没有节点
return null; // 则不需要建立二叉树,退出递归
}
int rootVal = postorder[postIndex]; // postIndex 指向 postorder 中当前树的根节点的值
int index = indcies.get(rootVal); // 获取当前根节点的值在 中序遍历数组 中的索引
TreeNode root = new TreeNode(rootVal); // 新建当前树的根节点
// 先构建右子树,再构建左子树,最后返回本次构建的二叉树
postIndex--; // 让 postIndex 指向右子树的根节点
root.right = build(index + 1, inRight); // 构建完右子树后,postIndex 指向左子树的根节点
root.left = build(inLeft, index - 1);
return root;
}
}