🚀 算法題 🚀

🌲 算法刷題專欄 | 面試必備算法 | 面試高頻算法 🍀
🌲 越難的東西,越要努力堅持，因為它具有很高的價值，算法就是這樣?
🌲 作者簡介：碩風和煒，CSDN-Java領域優質創作者🏆，保研|國家獎學金|高中學習JAVA|大學完善JAVA開發技術棧|面試刷題|面經八股文|經驗分享|好用的網站工具分享💎💎💎
🌲 恭喜你發現一枚寶藏博主,趕快收入囊中吧🌻
🌲 人生如棋，我愿為卒，行動雖慢，可誰曾見我后退一步？🎯🎯

🚀 算法題 🚀

🚩 題目鏈接

• 496. 下一個更大元素 I

? 題目描述

nums1 中數字 x 的 下一個更大元素 是指 x 在 nums2 中對應位置 右側 的 第一個 比 x 大的元素。

給你兩個 沒有重復元素 的數組 nums1 和 nums2 ，下標從 0 開始計數，其中nums1 是 nums2 的子集。

對于每個 0 <= i < nums1.length ，找出滿足 nums1[i] == nums2[j] 的下標 j ，并且在 nums2 確定 nums2[j] 的 下一個更大元素 。如果不存在下一個更大元素，那么本次查詢的答案是 -1 。

返回一個長度為 nums1.length 的數組 ans 作為答案，滿足 ans[i] 是如上所述的 下一個更大元素 。

示例 1：

輸入：nums1 = [4,1,2], nums2 = [1,3,4,2].
輸出：[-1,3,-1]
解釋：nums1 中每個值的下一個更大元素如下所述：

• 4 ，用加粗斜體標識，nums2 = [1,3,4,2]。不存在下一個更大元素，所以答案是 -1 。
• 1 ，用加粗斜體標識，nums2 = [1,3,4,2]。下一個更大元素是 3 。
• 2 ，用加粗斜體標識，nums2 = [1,3,4,2]。不存在下一個更大元素，所以答案是 -1 。
  示例 2：

輸入：nums1 = [2,4], nums2 = [1,2,3,4].
輸出：[3,-1]
解釋：nums1 中每個值的下一個更大元素如下所述：

• 2 ，用加粗斜體標識，nums2 = [1,2,3,4]。下一個更大元素是 3 。
• 4 ，用加粗斜體標識，nums2 = [1,2,3,4]。不存在下一個更大元素，所以答案是 -1 。

提示：

1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 104
nums1和nums2中所有整數 互不相同
nums1 中的所有整數同樣出現在 nums2 中

進階：你可以設計一個時間復雜度為 O(nums1.length + nums2.length) 的解決方案嗎？

🌟 求解思路&實現代碼&運行結果

---

? 單調棧

🥦 求解思路

1. 題目需要我們，nums1 中數字 x 的 下一個更大元素 是指 x 在 nums2 中對應位置 右側 的 第一個 比 x 大的元素。nums2中包含nums1中的元素，我們通過單調棧先在nums2中找下一個更大的元素，該過程我們額外借助一個HashMap來實現，最后在nums1中去尋找即可。
2. 有了基本的思路，接下來我們就來通過代碼來實現一下。

🥦 實現代碼

class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {int n = nums1.length;int m = nums2.length;int[] ans = new int[n];Deque<Integer> queue = new LinkedList<>();HashMap<Integer, Integer> map = new HashMap<>();for (int i = 0; i < m; i++) {while (!queue.isEmpty() && nums2[i] > nums2[queue.peekLast()]) {int j = queue.pollLast();map.put(nums2[j], nums2[i]);}queue.addLast(i);}for (int i = 0; i < n; i++) {ans[i] = map.getOrDefault(nums1[i], -1);}return ans;}
}

🥦 運行結果

---

💬 共勉

最后，我想和大家分享一句一直激勵我的座右銘，希望可以與大家共勉！