我是小張同學(xué)，立志用更簡(jiǎn)潔的代碼做更高效的表達(dá)

---

給你兩個(gè) 沒有重復(fù)元素 的數(shù)組 nums1 和 nums2 ，其中nums1 是 nums2 的子集。

請(qǐng)你找出 nums1 中每個(gè)元素在 nums2 中的下一個(gè)比其大的值。

nums1 中數(shù)字 x 的下一個(gè)更大元素是指 x 在 nums2 中對(duì)應(yīng)位置的右邊的第一個(gè)比 x 大的元素。如果不存在，對(duì)應(yīng)位置輸出 -1 。

示例 1:
輸入: nums1 = [4,1,2], nums2 = [1,3,4,2].
輸出: [-1,3,-1]
解釋:
對(duì)于 num1 中的數(shù)字 4 ，你無法在第二個(gè)數(shù)組中找到下一個(gè)更大的數(shù)字，因此輸出 -1 。
對(duì)于 num1 中的數(shù)字 1 ，第二個(gè)數(shù)組中數(shù)字1右邊的下一個(gè)較大數(shù)字是 3 。
對(duì)于 num1 中的數(shù)字 2 ，第二個(gè)數(shù)組中沒有下一個(gè)更大的數(shù)字，因此輸出 -1 。

示例 2:
輸入: nums1 = [2,4], nums2 = [1,2,3,4].
輸出: [3,-1]
解釋:
對(duì)于 num1 中的數(shù)字 2 ，第二個(gè)數(shù)組中的下一個(gè)較大數(shù)字是 3 。
對(duì)于 num1 中的數(shù)字 4 ，第二個(gè)數(shù)組中沒有下一個(gè)更大的數(shù)字，因此輸出 -1 。

提示：
1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 104
nums1和nums2中所有整數(shù) 互不相同
nums1 中的所有整數(shù)同樣出現(xiàn)在 nums2 中

---

核心思路：單調(diào)棧（在不改變數(shù)組順序的前提下有序）

做法：將nums2中的所有數(shù)據(jù)是否有下一個(gè)更大元素都求出來，存入哈希表，最后按nums1的順序查詢哈希表即可

一旦要求下一個(gè)更大的元素，就是用單調(diào)棧解，力扣題庫相似的題目都是這個(gè)解法。

---

class Solution { public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {unordered_map<int, int>um;stack<int>s;for (int i = nums2.size() - 1; i >= 0; --i) {int num = nums2[i];while (!s.empty() && num >= s.top()) {s.pop();}um[num] = (s.empty() ? -1 : s.top());s.push(num);}vector<int>res(nums1.size());for(int i = 0; i < nums1.size(); i++) {res[i] = um[nums1[i]];}return res;} };

總結(jié)

以上是生活随笔為你收集整理的Leecode 496. 下一个更大元素 I——Leecode每日一题系列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。