739. 每日溫度

給定一個整數數組?temperatures?，表示每天的溫度，返回一個數組?answer?，其中?answer[i]?是指對于第?i?天，下一個更高溫度出現在幾天后。如果氣溫在這之后都不會升高，請在該位置用?0?來代替。

示例 1:

輸入: temperatures = [73,74,75,71,69,72,76,73]
輸出:?[1,1,4,2,1,1,0,0]

示例 2:

輸入: temperatures = [30,40,50,60]
輸出:?[1,1,1,0]

示例 3:

輸入: temperatures = [30,60,90]
輸出: [1,1,0]

提示：

• 1 <=?temperatures.length <= 105
• 30 <=?temperatures[i]?<= 100

思路:

首先想到的當然是暴力解法，兩層for循環,時間復雜度是O(n^2)

單調棧的解法:時間復雜度為O(n)

什么時候用單調棧呢？

通常是一維數組，要尋找任一個元素的右邊或者左邊第一個比自己大或者小的元素的位置，此時我們就要想到可以用單調棧了。時間復雜度為O(n)。

單調棧的本質是空間換時間

首先要明確如下幾點：

1.單調棧里存放的元素是什么？

單調棧里只需要存放元素的下標i就可以了，如果需要使用對應的元素，直接T[i]就可以獲取。

2.單調棧里元素是遞增呢？ 還是遞減呢？

使用遞增循序（再強調一下是指從棧頭到棧底的順序）

圖解:

class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] result=new int[temperatures.length];List<Integer> list=new LinkedList<>();for(int i=0;i<temperatures.length;i++){while(list.size()>0&&temperatures[list.get(list.size()-1)]<temperatures[i]){int index=list.get(list.size()-1);result[index]=i-index;list.remove(list.size()-1);}list.add(i);}return result;}
}

---

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)?的解決方案嗎？

思路:本題與上題思路一致,只是不是求nums2中所有數的下一個更大書,而是求其子集nums1中每個數的在nums2中的下一個更大數,所以我們要將nums1的值和坐標存下來

此外,本題求下一個更大數,不是求坐標,所以單調棧中存放數而不是坐標了

 class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums1.length; i++) {map.put(nums1[i], i);//記錄下nums1中的數據以及它們對應的下標}int result[] = new int[nums1.length];//初始化Arrays.fill(result, -1);//單調棧List<Integer> list = new LinkedList<>();for (int i = 0; i < nums2.length; i++) {//當棧不為空,且nums2[i]>棧頂元素時,找到了棧頂元素的下一個更大值了while (list.size() > 0 && nums2[i] > list.get(list.size() - 1)) {//如果棧頂元素是nums1中的元素if (map.containsKey(list.get(list.size() - 1))) {//記錄下這個更大值//求棧頂元素int num = list.get(list.size() - 1);//求棧頂元素在nums1中的位置,和記錄結果result[map.get(num)] = nums2[i];}list.remove(list.size() - 1);}list.add(nums2[i]);}return result;}
}

---

503. 下一個更大元素 II

給定一個循環數組?nums?（?nums[nums.length - 1]?的下一個元素是?nums[0]?），返回?nums?中每個元素的?下一個更大元素?。

數字?x?的?下一個更大的元素?是按數組遍歷順序，這個數字之后的第一個比它更大的數，這意味著你應該循環地搜索它的下一個更大的數。如果不存在，則輸出?-1?。

示例 1:

輸入: nums = [1,2,1]
輸出: [2,-1,2]
解釋: 第一個 1 的下一個更大的數是 2；
數字 2 找不到下一個更大的數； 
第二個 1 的下一個最大的數需要循環搜索，結果也是 2。

示例 2:

輸入: nums = [1,2,3,4,3]
輸出: [2,3,4,-1,4]

提示:

• 1 <= nums.length <= 104
• -109?<= nums[i] <= 109

思路:本題與上題類似,可以將兩個nums拼起來,然后利用單調棧求出每個數的下一個更大的數

class Solution {public int[] nextGreaterElements(int[] nums) {int[] result=new int[nums.length];List<Integer>list=new LinkedList<>();Arrays.fill(result,-1);for(int i=0;i<2*nums.length;i++){while(list.size()>0&&nums[i%nums.length]>nums[list.get(list.size()-1)]){int index=list.get(list.size()-1);result[index]=nums[i%nums.length];list.removeLast();}list.add(i%nums.length);}return result;}
}