作者推荐

【动态规划】【广度优先】LeetCode2258:逃离火灾

本文涉及的基础知识点

单调栈分类、封装和总结

二分查找算法合集

题目

给你一个下标从 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记录所有没有比它大的元素的元素所有mValueIndexmValueIndex，记录所有找到更大的元素，但没找到第二个更大元素的元素所有。键：值；值：索引。

二分查找优化

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

void Assert(const vector& v1, const vector& v2)

{

if (v1.size() != v2.size())

{

assert(false);

return;

}

for (int i = 0; i < v1.size(); i++)

{

assert(v1[i] == v2[i]);

}

}

template

void Assert(const T& t1, const T& t2)

{

assert(t1 == t2);

}

int main()

{

vector nums;

{

Solution slu;

nums = { 2, 4, 0, 9, 6 };

auto res = slu.secondGreaterElement(nums);

Assert(vector{9, 6, 6, -1, -1}, res);

}

{

Solution slu;

nums = { 3,3 };

auto res = slu.secondGreaterElement(nums);

Assert(vector{ -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{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 secondGreaterElement(vector& nums) {

stack staNoMax,staNoMax2;

vector vRet(nums.size(), -1);

vector 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++**实现。

好文阅读

评论可见，请评论后查看内容，谢谢！！！
 您阅读本篇文章共花了：