Go語(yǔ)言題解LeetCode下一個(gè)更大元素示例詳解
題目描述
原題鏈接 :
496. 下一個(gè)更大元素 I - 力扣(LeetCode) (leetcode-cn.com)
nums1
中數(shù)字 x
的 下一個(gè)更大元素 是指 x
在 nums2
中對(duì)應(yīng)位置 右側(cè) 的 第一個(gè) 比 x
大的元素。
給你兩個(gè) 沒(méi)有重復(fù)元素 的數(shù)組 nums1
和 nums2
,下標(biāo)從 0
開(kāi)始計(jì)數(shù),其中nums1
是 nums2
的子集。
對(duì)于每個(gè) 0 <= i < nums1.length
,找出滿足 nums1[i] == nums2[j]
的下標(biāo) j
,并且在 nums2
確定 nums2[j]
的 下一個(gè)更大元素 。如果不存在下一個(gè)更大元素,那么本次查詢的答案是 -1
。
返回一個(gè)長(zhǎng)度為 nums1.length
的數(shù)組 ans
作為答案,滿足 ans[i]
是如上所述的 下一個(gè)更大元素 。
示例 1:
輸入:nums1 = [4,1,2], nums2 = [1,3,4,2]. 輸出:[-1,3,-1] 解釋:nums1 中每個(gè)值的下一個(gè)更大元素如下所述: - 4 ,用加粗斜體標(biāo)識(shí),nums2 = [1,3,4,2]。不存在下一個(gè)更大元素,所以答案是 -1 。 - 1 ,用加粗斜體標(biāo)識(shí),nums2 = [1,3,4,2]。下一個(gè)更大元素是 3 。 - 2 ,用加粗斜體標(biāo)識(shí),nums2 = [1,3,4,2]。不存在下一個(gè)更大元素,所以答案是 -1 。
示例 2:
輸入:nums1 = [2,4], nums2 = [1,2,3,4]. 輸出:[3,-1] 解釋:nums1 中每個(gè)值的下一個(gè)更大元素如下所述: - 2 ,用加粗斜體標(biāo)識(shí),nums2 = [1,2,3,4]。下一個(gè)更大元素是 3 。 - 4 ,用加粗斜體標(biāo)識(shí),nums2 = [1,2,3,4]。不存在下一個(gè)更大元素,所以答案是 -1 。
提示:
1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 10^4
- nums1和nums2中所有整數(shù) 互不相同
- nums1 中的所有整數(shù)同樣出現(xiàn)在 nums2 中
思路分析
這種題目典型的使用單調(diào)棧就行了啊。
- 元素入棧之后,其下面的元素一定是其左邊第一個(gè)比它小的數(shù);(可用來(lái)求每個(gè)元素左邊更小的第一個(gè)元素)
- 若在元素插入之前,棧頂元素比插入元素更大,那么棧頂元素一定是待插入元素左邊一個(gè)更大的數(shù)
- 若在元素插入之前,棧頂元素比插入元素更大,那么棧頂元素一定是所有需要出棧的元素右邊更小的數(shù);(可用來(lái)求每個(gè)元素右邊更小的第一個(gè)元素)
- 最后一定會(huì)留下最小的數(shù)(對(duì)較小 的數(shù)更有利)
AC 代碼
class Solution { public: vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) { map<int,int> PMap; stack<int> DStack; vector<int> result; for(int i=nums2.size()-1;i>=0;i--){ if(DStack.empty()){ PMap.insert({nums2[i],-1}); DStack.push(nums2[i]); } else if(DStack.top()>nums2[i]){ PMap.insert({nums2[i],DStack.top()}); DStack.push(nums2[i]); } else{ while(!DStack.empty()&&DStack.top()<nums2[i]) DStack.pop(); if(DStack.empty()) PMap.insert({nums2[i],-1}); else PMap.insert({nums2[i],DStack.top()}); DStack.push(nums2[i]); } } for(int i=0;i<nums1.size();i++) result.push_back(PMap[nums1[i]]); return result; } };
以上就是Go語(yǔ)言題解LeetCode下一個(gè)更大元素示例詳解的詳細(xì)內(nèi)容,更多關(guān)于go題解下一個(gè)更大元素的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
GO語(yǔ)言標(biāo)準(zhǔn)錯(cuò)誤處理機(jī)制error用法實(shí)例
這篇文章主要介紹了GO語(yǔ)言標(biāo)準(zhǔn)錯(cuò)誤處理機(jī)制error用法,實(shí)例分析了錯(cuò)誤處理機(jī)制的具體用法,具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2014-12-12詳解Golang中string的實(shí)現(xiàn)原理與高效使用
在Go語(yǔ)言中,無(wú)論是字符串常量、字符串變量還是代碼中出現(xiàn)的字符串字面量,它們的類型都被統(tǒng)一設(shè)置為string,下面就跟隨小編一起來(lái)了解一下Golang中string的實(shí)現(xiàn)原理與高效使用吧2024-01-01Go語(yǔ)言并發(fā)編程基礎(chǔ)上下文概念詳解
這篇文章主要為大家介紹了Go語(yǔ)言并發(fā)編程基礎(chǔ)上下文示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2022-08-08Golang通道阻塞情況與通道無(wú)阻塞實(shí)現(xiàn)小結(jié)
本文主要介紹了Golang通道阻塞情況與通道無(wú)阻塞實(shí)現(xiàn)小結(jié),詳細(xì)解析了通道的類型、操作方法以及垃圾回收機(jī)制,從基礎(chǔ)概念到高級(jí)應(yīng)用,具有一定的參考價(jià)值,感興趣的可以了解一下2024-03-03Go語(yǔ)言自定義包構(gòu)建自己的編程工具庫(kù)
Go 語(yǔ)言的強(qiáng)大不僅體現(xiàn)在其內(nèi)置功能上,還在于其支持自定義包,這為開(kāi)發(fā)者提供了極大的靈活性和可擴(kuò)展性,本文將深入介紹如何創(chuàng)建、使用和管理自定義包,探索 Go 語(yǔ)言包的奧秘,打造屬于你的編程工具庫(kù)2023-11-11Golang Socket Server自定義協(xié)議的簡(jiǎn)單實(shí)現(xiàn)方案
這篇文章主要介紹了Golang Socket Server自定義協(xié)議的簡(jiǎn)單實(shí)現(xiàn)方案,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-12-12Golang 性能基準(zhǔn)測(cè)試(benchmark)詳解
Golang性能基準(zhǔn)測(cè)試可以幫助開(kāi)發(fā)人員比較不同的實(shí)現(xiàn)方式對(duì)性能的影響,以便優(yōu)化程序,本文就來(lái)講解一下如何使用Golang的性能基準(zhǔn)測(cè)試功能,需要的朋友可以參考下2023-06-06