739. 每日溫度

題目鏈接： 739. 每日溫度
文檔講解：代碼隨想錄
狀態：不會

思路：
這道題需要找到下一個更大元素。
使用棧來存儲未找到更高溫度的下標，那么棧中的下標對應的溫度從棧底到棧頂是遞減的。這意味著，棧頂元素的溫度是當前溫度數組中未找到更高溫度的最高溫度的下標。

總結成一句話就是：在解決“下一個更大元素”問題時，遍歷數組時，如果當前元素大于棧頂元素，就先將棧頂元素出棧并更新其結果，然后將當前元素入棧。

題解：

    public int[] dailyTemperatures(int[] temperatures) {int n = temperatures.length;int[] res = new int[n];  // 初始化結果數組，長度與溫度數組相同Deque<Integer> stack = new LinkedList<>();  // 初始化棧，用于存儲未找到更高溫度的下標for (int i = 0; i < n; i++) {  // 遍歷溫度數組// 如果當前溫度高于棧頂元素的溫度，則更新結果數組// 使用棧來存儲未找到更高溫度的下標,棧中的下標對應的溫度從棧底到棧頂是遞減的。// 這意味著，棧頂元素的溫度是當前溫度數組中未找到更高溫度的最高溫度的下標。while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peekLast()]) {int index = stack.pollLast();  // 彈出棧頂元素res[index] = i - index;  // 計算當前下標與棧頂元素下標的差值，并更新結果數組}stack.addLast(i);  // 將當前下標添加到棧中}return res;  // 返回結果數組}

496.下一個更大元素 I

題目鏈接： 496.下一個更大元素 I
文檔講解：代碼隨想錄
狀態：用的另一種方法

單調棧思路：

這題是屬于找下一個更大元素，所以可以使用單調棧。

和每日溫度類似，可以對nums2使用單調棧，即當前元素大于棧頂元素，就先將棧頂元素出棧并更新其結果，然后將當前元素入棧。但是這道題需要從nums2中找nums1元素，并且res的更新是按照nums1來的，所以可以將nums1中的元素存入哈希表中，如果nums2中遍歷到的元素是nums1中的元素，則額外更新res。

題解：

    // 方法1: 暴力+哈希解法public int[] nextGreaterElement(int[] nums1, int[] nums2) {int[] res = new int[nums1.length];  // 結果數組HashMap<Integer, Integer> map = new HashMap<>();  // 存儲 nums2 中元素的下標for (int i = 0; i < nums2.length; i++) {map.put(nums2[i], i);  // 將 nums2 中的元素及其下標放入 map 中}for (int i = 0; i < nums1.length; i++) {Integer index = map.get(nums1[i]);  // 獲取 nums1 中元素在 nums2 中的下標for (int j = index; j < nums2.length; j++) {if (nums2[j] > nums1[i]) {  // 找到第一個比 nums1[i] 大的元素res[i] = nums2[j];  // 更新結果數組break;} else {res[i] = -1;  // 未找到更大元素，默認設置為 -1}}}return res;}// 方法2: 單調棧public int[] nextGreaterElement2(int[] nums1, int[] nums2) {int[] res = new int[nums1.length];  // 結果數組Arrays.fill(res, -1);  // 初始化結果數組為 -1HashMap<Integer, Integer> map = new HashMap<>();  // 存儲 nums1 中元素的下標Deque<Integer> stack = new LinkedList<>();  // 初始化單調棧for (int i = 0; i < nums1.length; i++) {map.put(nums1[i], i);  // 將 nums1 中的元素及其下標放入 map 中}for (int i = 0; i < nums2.length; i++) {// 如果當前元素 nums2[i] 大于棧頂元素，則更新棧頂元素在結果數組中的值while (!stack.isEmpty() && nums2[stack.peekLast()] < nums2[i]) {Integer num = nums2[stack.pollLast()];  // 彈出棧頂元素if (map.containsKey(num)) {res[map.get(num)] = nums2[i];  // 更新結果數組中對應位置的值}}stack.addLast(i);  // 將當前元素下標加入棧中}return res;}

503.下一個更大元素II

題目鏈接： 503.下一個更大元素II
文檔講解：代碼隨想錄
狀態：磕磕絆絆

思路：
最直接的想法把兩個數組拼接在一起，然后使用單調棧求下一個最大值。
優化的話在遍歷的過程中模擬走了兩邊nums。

題解：

   public int[] nextGreaterElements(int[] nums) {int n = nums.length; // 獲取數組的長度int[] res = new int[n]; // 結果數組，用來存儲每個元素的下一個更大元素Arrays.fill(res, -1); // 初始化結果數組，默認值為-1Deque<Integer> stack = new LinkedList<>(); // 單調棧，用來存儲數組元素的下標// 遍歷2倍長度的數組，模擬循環數組for (int i = 0; i < 2 * n; i++) {// 如果當前元素大于棧頂元素，則更新棧頂元素在結果數組中的值while (!stack.isEmpty() && nums[i % n] > nums[stack.peekLast()]) {res[stack.pollLast()] = nums[i % n]; // 更新結果數組中對應下標的值}// 只將前n個元素的下標入棧if (i < n) {stack.addLast(i); // 將當前下標入棧}}return res; // 返回結果數組}