题目
给你一个下标从 0 开始的非负整数数组 nums 。对于 nums 中每一个整数，你必须找到对应元素的 第二大 整数。
如果 nums[j] 满足以下条件，那么我们称它为 nums[i] 的 第二大 整数：
j > i
nums[j] > nums[i]
恰好存在 一个 k 满足 i < k < j 且 nums[k] > nums[i] 。
如果不存在 nums[j] ，那么第二大整数为 -1 。
比方说，数组 [1, 2, 4, 3] 中，1 的第二大整数是 4 ，2 的第二大整数是 3 ，3 和 4 的第二大整数是 -1 。
请你返回一个整数数组 answer ，其中 answer[i]是 nums[i] 的第二大整数。
示例 1：
输入：nums = [2,4,0,9,6]
输出：[9,6,6,-1,-1]
解释：
下标为 0 处：2 的右边，4 是大于 2 的第一个整数，9 是第二个大于 2 的整数。
下标为 1 处：4 的右边，9 是大于 4 的第一个整数，6 是第二个大于 4 的整数。
下标为 2 处：0 的右边，9 是大于 0 的第一个整数，6 是第二个大于 0 的整数。
下标为 3 处：右边不存在大于 9 的整数，所以第二大整数为 -1 。
下标为 4 处：右边不存在大于 6 的整数，所以第二大整数为 -1 。
所以我们返回 [9,6,6,-1,-1] 。
示例 2：
输入：nums = [3,3]
输出：[-1,-1]
解释：
由于每个数右边都没有更大的数，所以我们返回 [-1,-1] 。
参数范围
1 <= nums.length <= 105
0 <= nums[i] <= 109
单调栈找更大的元素，有序映射寻找第二个更大元素
时间复杂度：O(nlogn)。枚举更大（第二个更大）元素，时间复杂度O(n)。有序映射的插入，时间复杂度O(logn)。
变量解释
| staNoMax | 记录所有没有比它大的元素的元素所有 |
| mValueIndex | mValueIndex，记录所有找到更大的元素，但没找到第二个更大元素的元素所有。键：值；值：索引。 |
二分查找优化
staNoMax是降序，当新增元素x的时候，所有小于x的元素都会出栈，所以x的前面如果有元素，则一定大于等于x。
由于staNoMax是降序，所以当x2大于等于x时，前面元素也大于x，所以无需继续查找。
** 注意**：
mValueInde先删除，否则增加的元素，马上删除。当前元素成了更大元素和下一个更大元素。
代码
核心代码
class Solution { public: vector secondGreaterElement(vector& nums) { stack staNoMax; std::multimap mValueIndex; vector vRet(nums.size(), -1); for (int i = 0; i < nums.size(); i++) { while (mValueIndex.size() && (mValueIndex.begin()->first < nums[i])) { vRet[mValueIndex.begin()->second] = nums[i]; mValueIndex.erase(mValueIndex.begin()); } while (staNoMax.size() && (nums[staNoMax.top()] < nums[i])) { mValueIndex.emplace(nums[staNoMax.top()],staNoMax.top()); staNoMax.pop(); } staNoMax.emplace(i); } return vRet; } };
测试用例
template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { assert(v1[i] == v2[i]); } } template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } int main() { vector<int> nums; { Solution slu; nums = { 2, 4, 0, 9, 6 }; auto res = slu.secondGreaterElement(nums); Assert(vector<int>{9, 6, 6, -1, -1}, res); } { Solution slu; nums = { 3,3 }; auto res = slu.secondGreaterElement(nums); Assert(vector<int>{ -1, -1}, res); } { Solution slu; nums = { 272, 238, 996, 406, 763, 164, 102, 948, 217 ,760,609,700,848 }; auto res = slu.secondGreaterElement(nums); Assert(vector<int>{406, 406, -1, 948, 848, 217, 217, -1, 609, -1, 848, -1, -1}, res); } //CConsole::Out(res); }
优化
mValueIndex新增元素之前，mValueIndex中的元素一定大于等于nums[i]，否则被删除了。新增加到mValueIndex的元素一定小于nums[i]。故之前增加的元素一定大于本次增加。 本次增加的是按升序加的，可以放到缓存中，按反顺序加入。这样：有序映射就优化成了栈。
class Solution { public: vector<int> secondGreaterElement(vector<int>& nums) { stack<int> staNoMax,staNoMax2; vector<int> vRet(nums.size(), -1); vector<int> vBuf; for (int i = 0; i < nums.size(); i++) { while (staNoMax2.size() && (nums[staNoMax2.top()] < nums[i])) { vRet[staNoMax2.top()] = nums[i]; staNoMax2.pop(); } while (staNoMax.size() && (nums[staNoMax.top()] < nums[i])) { vBuf.emplace_back(staNoMax.top()); staNoMax.pop(); } staNoMax.emplace(i); for (auto it = vBuf.rbegin(); it != vBuf.rend(); ++it) { staNoMax2.emplace(*it); } vBuf.clear(); } return vRet; } };
2023年3月版 二分查找
bool GreaterPairInt(const std::pair& p,int iData ) { return p.first > iData ; } class Solution { public: vector secondGreaterElement(vector& nums) { m_c = nums.size(); //vLeftFirstLess[i] i是它的下一个更大数 vector vLeftFirstLess(m_c); { vector> vStack; for (int i = m_c - 1; i >= 0; i–) { int iNum = std::lower_bound(vStack.begin(), vStack.end(), nums[i], GreaterPairInt) - vStack.begin(); if (iNum > 0) { const int iFristGreaterIndex = vStack[iNum - 1].second;; vLeftFirstLess[iFristGreaterIndex].push_back(i); } while (vStack.size() && (nums[i] >= vStack.back().first)) { vStack.pop_back(); } vStack.emplace_back(nums[i], i); } } vector vRet(m_c, -1); { vector> vStack; for (int i = m_c - 1; i >= 0; i–) { for (auto& it : vLeftFirstLess[i]) { int iNum = std::lower_bound(vStack.begin(), vStack.end(), nums[it], GreaterPairInt) - vStack.begin(); if (iNum > 0) { const int iFristGreaterIndex = vStack[iNum - 1].second;; vRet[it] = nums[iFristGreaterIndex]; } } while (vStack.size() && (nums[i] >= vStack.back().first)) { vStack.pop_back(); } vStack.emplace_back(nums[i], i); } } return vRet; } int m_c; };
2023年9月版
class Solution { public: vector secondGreaterElement(vector& nums) { m_c = nums.size(); stack sta; std::priority_queue, vector>, greater<>> minHeap; vector vRet(m_c, -1); for (int i = 0; i < m_c; i++) { const int& n = nums[i]; while (minHeap.size() && (minHeap.top().first < n)) { vRet[minHeap.top().second] = n; minHeap.pop(); } while (sta.size() && (nums[sta.top()] < n)) { minHeap.emplace(nums[sta.top()], sta.top()); sta.pop(); } sta.emplace(i); } return vRet; } int m_c; };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
。也就是我们常说的专业的人做专业的事。 |
|如果程序是一条龙，那算法就是他的是睛|
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
