8.[计算机专业要不要读研！](https://mp.weixin.qq.com/s/c9v1L3IjqiXtkNH7sOMAdg)

9.[秋招和提前批都越来越提前了....](https://mp.weixin.qq.com/s/SNFiRDx8CKyjhTPlys6ywQ)

10.[你的简历里「专业技能」写的够专业么？](https://mp.weixin.qq.com/s/bp6y-e5FVN28H9qc8J9zrg)

11.[对于秋招，实习生也有烦恼....](https://mp.weixin.qq.com/s/ka07IPryFnfmIjByFFcXDg)

1.[单调栈：每日温度](./problems/0739.每日温度.md)

2.[单调栈：下一个更大元素I](./problems/0496.下一个更大元素I.md)

3.[单调栈：下一个更大元素II](./problems/0503.下一个更大元素II.md)

可以递归中序遍历将二叉搜索树转变成一个数组，代码如下：

vector<int> vec;

voidtraversal(TreeNode* root) {

if (root == NULL) return;

整体代码如下：

classSolution {

private:

vector<int> vec;

代码如下：

classSolution {

public:

TreeNode* pre = NULL; // 用来记录前一个节点

迭代法中序遍历稍加改动就可以了，代码如下：

classSolution {

public:

bool isValidBST(TreeNode* root) {

咋眼一看这道题目和[二叉树：看看这些树的最大深度](https://mp.weixin.qq.com/s/guKwV-gSNbA1CcbvkMtHBg)很像，其实有很大区别。

咋眼一看这道题目和[104.二叉树的最大深度](https://mp.weixin.qq.com/s/guKwV-gSNbA1CcbvkMtHBg)很像，其实有很大区别。

这里强调一波概念：

因为求深度可以从上到下去查 所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）

有的同学一定疑惑，为什么[二叉树：看看这些树的最大深度](https://mp.weixin.qq.com/s/guKwV-gSNbA1CcbvkMtHBg)中求的是二叉树的最大深度，也用的是后序遍历。

有的同学一定疑惑，为什么[104.二叉树的最大深度](https://mp.weixin.qq.com/s/guKwV-gSNbA1CcbvkMtHBg)中求的是二叉树的最大深度，也用的是后序遍历。

**那是因为代码的逻辑其实是求的根节点的高度，而根节点的高度就是这颗树的最大深度，所以才可以使用后序遍历。**

在[二叉树：看看这些树的最大深度](https://mp.weixin.qq.com/s/guKwV-gSNbA1CcbvkMtHBg)中，如果真正求取二叉树的最大深度，代码应该写成如下：（前序遍历）

在[104.二叉树的最大深度](https://mp.weixin.qq.com/s/guKwV-gSNbA1CcbvkMtHBg)中，如果真正求取二叉树的最大深度，代码应该写成如下：（前序遍历）

classSolution {

publicbooleanisBalanced(TreeNoderoot) {

return height;

}

}

Python：

return a

}

#"diff-40df71151a9f9143c69e16862a20ec128455282da0d6394eb034bc3fc10455d3-594-593-0" data-selected="false" role="gridcell" tabindex="-1" valign="top">594

varisBalanced=function(root) {

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

输入: nums =[1,1,1,2,2,3], k = 2

输出:[1,2]

*输入: nums =[1,1,1,2,2,3], k = 2

*输出:[1,2]

示例 2:

输入: nums =[1], k = 1

输出:[1]

*输入: nums =[1], k = 1

*输出:[1]

提示：

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。

你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。

你可以按任意顺序返回答案。

*你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。

*你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

*题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。

*你可以按任意顺序返回答案。

寻找前k个最大元素流程如图所示：（图中的频率只有三个，所以正好构成一个大小为3的小顶堆，如果频率更多一些，则用这个小顶堆进行扫描）



我们来看一下C++代码：

链接：https://leetcode-cn.com/problems/next-greater-element-ii/

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

示例 1:

* 输入:[1,2,1]

* 输出:[2,-1,2]

* 解释: 第一个 1 的下一个更大的数是 2；数字 2 找不到下一个更大的数；第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

做本题之前建议先做[739. 每日温度](https://mp.weixin.qq.com/s/YeQ7eE0-hZpxJfJJziq25Q) 和[496.下一个更大元素 I](https://mp.weixin.qq.com/s/U0O6XkFOe-RMXthPS16sWQ)。

这道题和[739. 每日温度](https://mp.weixin.qq.com/s/YeQ7eE0-hZpxJfJJziq25Q)也几乎如出一辙。

不同的时候本题要循环数组了。

关于单调栈的讲解我在题解[739. 每日温度](https://mp.weixin.qq.com/s/YeQ7eE0-hZpxJfJJziq25Q)中已经详细讲解了。

本篇我侧重与说一说，如何处理循环数组。

相信不少同学看到这道题，就想那我直接把两个数组拼接在一起，然后使用单调栈求下一个最大值不就行了！

确实可以！

讲两个nums数组拼接在一起，使用单调栈计算出每一个元素的下一个最大值，最后再把结果集即result数组resize到原数组大小就可以了。

代码如下：

classSolution {

public:

vector<int> nextGreaterElements(vector<int>& nums) {

// 拼接一个新的nums

vector<int> nums1(nums.begin(), nums.end());

nums.insert(nums.end(), nums1.begin(), nums1.end());

// 用新的nums大小来初始化result

vector<int> result(nums.size(), -1);

if (nums.size() == 0) return result;

st.push(i);

}

result.resize(nums.size() /2);

return result;

}

};

这种写法确实比较直观，但做了很多无用操作，例如修改了nums数组，而且最后还要把result数组resize回去。

resize倒是不费时间，是O(1)的操作，但扩充nums数组相当于多了一个O(n)的操作。

其实也可以不扩充nums，而是在遍历的过程中模拟走了两边nums。

代码如下：

classSolution {

public:

vector<int> nextGreaterElements(vector<int>& nums) {

vector<int> result(nums.size(), -1);

if (nums.size() == 0) return result;

stack<int> st;

for (int i = 0; i < nums.size() * 2; i++) {

// 模拟遍历两边nums，注意一下都是用i % nums.size()来操作

while (!st.empty() && nums[i % nums.size()] > nums[st.top()]) {

result[st.top()] = nums[i % nums.size()];

st.pop();

}

st.push(i % nums.size());

}

return result;

}

};

You can’t perform that action at this time.

©2009-2025 Movatter.jp