代碼隨想錄-Day53

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]
在這里插入圖片描述

方法一：

class Solution {// 版本 1public int[] dailyTemperatures(int[] temperatures) {int lens=temperatures.length;int []res=new int[lens];/**如果當前遍歷的元素 大于棧頂元素，表示 棧頂元素的 右邊的最大的元素就是 當前遍歷的元素，所以彈出 棧頂元素，并記錄如果棧不空的話，還要考慮新的棧頂與當前元素的大小關系否則的話，可以直接入棧。注意，單調棧里 加入的元素是 下標。*/Deque<Integer> stack=new LinkedList<>();stack.push(0);for(int i=1;i<lens;i++){if(temperatures[i]<=temperatures[stack.peek()]){stack.push(i);}else{while(!stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()]){res[stack.peek()]=i-stack.peek();stack.pop();}stack.push(i);}}return  res;}

這段代碼是用于解決「每日溫度」問題的Java實現，這個問題的目標是給定一個整數數組 temperatures，其中每個元素表示每天的溫度，返回一個新的數組，其中每個元素表示直到未來幾天才會出現更高的溫度的天數。如果不存在未來幾天會出現更高的溫度，那么該位置的值為0。

代碼解析

初始化:
- 創建一個與 temperatures 長度相同的數組 res，用于存放結果。
- 使用一個單調棧 stack，數據結構為 Deque，在Java中通常使用 LinkedList 實現，用于存儲下標。
遍歷并維護單調棧:
- 遍歷 temperatures 數組中的每個元素。
- 對于當前遍歷到的元素 temperatures[i]：
  - 如果該元素小于等于棧頂元素對應的溫度，即 temperatures[i] <= temperatures[stack.peek()]，則將當前下標 i 入棧。
  - 否則，進入一個while循環：
    - 當棧不為空且當前元素大于棧頂元素對應的溫度時，彈出棧頂元素，并計算棧頂元素下標到當前下標 i 的距離，即 i - stack.peek()，并將這個距離存入結果數組 res 的對應位置。
    - 繼續循環，直到棧為空或當前元素不大于棧頂元素對應的溫度。
  - 最后，將當前下標 i 入棧。
返回結果:
- 返回結果數組 res，其中每個元素表示直到未來幾天才會出現更高的溫度的天數。

時間復雜度和空間復雜度

時間復雜度: O(n)，其中 n 是數組 temperatures 的長度。每個元素至多被放入和彈出棧一次。
空間復雜度: O(n)，需要一個大小為 n 的結果數組 res 和一個單調棧 stack。

總結

這段代碼通過使用單調棧的策略，有效地解決了每日溫度問題，能夠快速找到每個溫度元素右邊第一個比它大的溫度元素的位置。單調棧是一種常用的數據結構，在處理與單調性相關的數組或序列問題時非常有用，例如尋找最近的更大或更小的元素、股票價格波動分析等。在實際應用中，掌握單調棧的原理和使用方法能夠幫助解決一系列經典問題，提高代碼效率。

方法二：

    //--------這 是一條分界線// 版本 2class Solution {public int[] dailyTemperatures(int[] temperatures) {int lens=temperatures.length;int []res=new int[lens];Deque<Integer> stack=new LinkedList<>();for(int i=0;i<lens;i++){while(!stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()]){res[stack.peek()]=i-stack.peek();stack.pop();}stack.push(i);}return  res;}

這段代碼同樣是用于解決「每日溫度」問題的Java實現，其目標與前一版本相同，即給定一個整數數組 temperatures，返回一個新的數組，其中每個元素表示直到未來幾天才會出現更高的溫度的天數。如果不存在未來幾天會出現更高的溫度，那么該位置的值為0。

代碼解析

初始化:
- 創建一個與 temperatures 長度相同的數組 res，用于存放結果。
- 使用一個單調棧 stack，數據結構為 Deque，在Java中通常使用 LinkedList 實現，用于存儲下標。
遍歷并維護單調棧:
- 遍歷 temperatures 數組中的每個元素。
- 對于當前遍歷到的元素 temperatures[i]：
  - 進入一個while循環，只要棧不為空且當前元素大于棧頂元素對應的溫度，執行以下操作：
    - 計算棧頂元素下標到當前下標 i 的距離，即 i - stack.peek()，并將這個距離存入結果數組 res 的對應位置。
    - 彈出棧頂元素。
  - 將當前下標 i 入棧。
返回結果:
- 返回結果數組 res，其中每個元素表示直到未來幾天才會出現更高的溫度的天數。

時間復雜度和空間復雜度

時間復雜度: O(n)，其中 n 是數組 temperatures 的長度。每個元素至多被放入和彈出棧一次。
空間復雜度: O(n)，需要一個大小為 n 的結果數組 res 和一個單調棧 stack。

版本對比

相比于版本1，版本2的代碼在遍歷過程中直接從頭開始，簡化了代碼邏輯，將入棧操作放在了while循環的外部。這種寫法同樣有效，且邏輯上更清晰，因為它避免了不必要的條件判斷（如版本1中的 temperatures[i] <= temperatures[stack.peek()]）。每次遍歷到新元素時，代碼首先處理棧中所有比當前元素小的元素，然后將當前元素入棧，這一過程確保了棧內的元素始終按溫度遞減的順序排列，即形成了一個單調遞減棧。

總結

通過使用單調棧的策略，版本2的代碼同樣有效地解決了每日溫度問題。這種實現方式不僅保持了良好的時間復雜度和空間復雜度，而且在代碼結構上更為精簡和直觀，有助于提高代碼的可讀性和維護性。單調棧在處理與單調性相關的數組或序列問題時是一種非常有用的工具，熟練掌握其使用方法對于解決一系列經典問題具有重要意義。

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 。

方法一：

class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {Stack<Integer> temp = new Stack<>();int[] res = new int[nums1.length];Arrays.fill(res,-1);HashMap<Integer, Integer> hashMap = new HashMap<>();for (int i = 0 ; i< nums1.length ; i++){hashMap.put(nums1[i],i);}temp.add(0);for (int i = 1; i < nums2.length; i++) {if (nums2[i] <= nums2[temp.peek()]) {temp.add(i);} else {while (!temp.isEmpty() && nums2[temp.peek()] < nums2[i]) {if (hashMap.containsKey(nums2[temp.peek()])){Integer index = hashMap.get(nums2[temp.peek()]);res[index] = nums2[i];}temp.pop();}temp.add(i);}}return res;}
}

這段代碼是用于解決「下一個更大元素 I」問題的Java實現。給定兩個沒有重復元素的數組 nums1 和 nums2，其中 nums1 是 nums2 的一個子集，目標是對于 nums1 中的每一個元素，找到在 nums2 中下一個更大的元素的值。如果沒有這樣的元素，那么輸出 -1。

代碼解析

初始化:
- 創建一個單調棧 temp，數據結構為 Stack，用于存儲 nums2 中元素的下標。
- 創建一個結果數組 res，初始化所有元素為 -1，長度與 nums1 相同。
- 創建一個哈希映射 hashMap，用于存儲 nums1 中元素及其在 res 數組中的下標，以便快速查找和更新結果。
遍歷并維護單調棧:
- 遍歷 nums2 數組中的每個元素。
- 對于當前遍歷到的元素 nums2[i]：
  - 如果該元素小于等于棧頂元素對應的值，即 nums2[i] <= nums2[temp.peek()]，則將當前下標 i 入棧。
  - 否則，進入一個while循環：
    - 當棧不為空且當前元素大于棧頂元素對應的值時，檢查棧頂元素是否在 nums1 中，如果是，則獲取該元素在 res 中的下標，并將當前元素的值賦給 res 的對應位置。
    - 繼續循環，直到棧為空或當前元素不大于棧頂元素對應的值。
  - 最后，將當前下標 i 入棧。
返回結果:
- 返回結果數組 res，其中每個元素表示 nums1 中對應元素在 nums2 中的下一個更大元素的值，若不存在則為 -1。

時間復雜度和空間復雜度

時間復雜度: O(m + n)，其中 m 和 n 分別是數組 nums1 和 nums2 的長度。每個元素至多被放入和彈出棧一次，哈希表的查找操作平均時間復雜度為 O(1)。
空間復雜度: O(n)，需要一個大小為 n 的單調棧 temp 和一個哈希映射 hashMap，以及一個結果數組 res。

總結

這段代碼通過使用單調棧和哈希映射的策略，有效地解決了下一個更大元素問題，能夠快速找到 nums1 中每個元素在 nums2 中下一個更大元素的值。單調棧是一種常用的數據結構，在處理與單調性相關的數組或序列問題時非常有用，結合哈希映射能夠進一步提高查找效率。在實際應用中，掌握這些數據結構和算法原理能夠幫助解決一系列經典問題，提高代碼效率和性能。

方法二：

// 版本2
class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {HashMap<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums1.length; i++) {map.put(nums1[i], i);}int[] res = new int[nums1.length];Stack<Integer> stack = new Stack<>();Arrays.fill(res, -1);for (int i = 0; i < nums2.length; i++) {while (!stack.isEmpty() && nums2[stack.peek()] < nums2[i]) {int pre = nums2[stack.pop()];if (map.containsKey(pre)) {res[map.get(pre)] = nums2[i];}}stack.push(i);}return res;}
}

這段代碼是用于解決「下一個更大元素 I」問題的另一種Java實現，其實現思路與之前解析的版本相似，但代碼結構和變量命名有所不同，旨在解決給定兩個沒有重復元素的數組 nums1 和 nums2，其中 nums1 是 nums2 的一個子集，對于 nums1 中的每一個元素，找到在 nums2 中下一個更大的元素的值。如果沒有這樣的元素，那么輸出 -1。

代碼解析

初始化:
- 創建一個哈希映射 map，用于存儲 nums1 中元素及其在 nums1 中的下標，以便快速查找和更新結果。
- 創建一個結果數組 res，初始化所有元素為 -1，長度與 nums1 相同。
- 創建一個單調棧 stack，數據結構為 Stack，用于存儲 nums2 中元素的下標。
構建哈希映射:
- 遍歷 nums1 數組，將每個元素及其在 nums1 中的下標存儲在 map 中。
遍歷并維護單調棧:
- 遍歷 nums2 數組中的每個元素。
- 對于當前遍歷到的元素 nums2[i]：
  - 如果棧不為空并且棧頂元素對應的值小于當前元素，即 nums2[stack.peek()] < nums2[i]，則：
    - 彈出棧頂元素，并獲取其值。
    - 如果彈出的元素在 nums1 中，即 map 中存在該元素，那么在 res 數組的對應位置填入當前元素的值。
  - 繼續這個過程，直到棧為空或者棧頂元素對應的值不再小于當前元素。
  - 最后，將當前下標 i 入棧。
返回結果:
- 返回結果數組 res，其中每個元素表示 nums1 中對應元素在 nums2 中的下一個更大元素的值，若不存在則為 -1。

時間復雜度和空間復雜度

時間復雜度: O(m + n)，其中 m 和 n 分別是數組 nums1 和 nums2 的長度。每個元素至多被放入和彈出棧一次，哈希表的查找操作平均時間復雜度為 O(1)。
空間復雜度: O(n)，需要一個大小為 n 的單調棧 stack 和一個哈希映射 map，以及一個結果數組 res。

總結

這段代碼同樣通過使用單調棧和哈希映射的策略，有效地解決了下一個更大元素問題，能夠快速找到 nums1 中每個元素在 nums2 中下一個更大元素的值。代碼結構清晰，邏輯直觀，是解決這類問題的一種典型且高效的方法。掌握這些數據結構和算法原理能夠幫助解決一系列經典問題，提高代碼效率和性能。在實際應用中，根據具體需求和場景選擇合適的數據結構和算法是非常重要的。

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]

class Solution {public int[] nextGreaterElements(int[] nums) {//邊界判斷if(nums == null || nums.length <= 1) {return new int[]{-1};}int size = nums.length;int[] result = new int[size];//存放結果Arrays.fill(result,-1);//默認全部初始化為-1Stack<Integer> st= new Stack<>();//棧中存放的是nums中的元素下標for(int i = 0; i < 2*size; i++) {while(!st.empty() && nums[i % size] > nums[st.peek()]) {result[st.peek()] = nums[i % size];//更新resultst.pop();//彈出棧頂}st.push(i % size);}return result;}
}

這段代碼是用于解決「下一個更大元素 II」問題的Java實現。給定一個循環數組 nums（數組中元素的下一個元素是數組的第一個元素），目標是返回一個數組，其中每個元素是原數組中下一個更大元素的值，如果沒有更大的元素，則對應位置的值為 -1。

代碼解析

初始化:
- 創建一個單調棧 st，數據結構為 Stack，用于存儲 nums 中元素的下標。
- 創建一個結果數組 result，初始化所有元素為 -1，長度與 nums 相同。
遍歷并維護單調棧:
- 遍歷 nums 數組兩次，即遍歷 2 * nums 的長度（考慮到循環數組的性質），使用模運算 i % size 來獲取實際數組下標。
- 對于當前遍歷到的元素 nums[i % size]：
  - 如果棧不為空并且棧頂元素對應的值小于當前元素，即 nums[st.peek()] < nums[i % size]，則：
    - 更新 result 數組中對應位置的值為當前元素的值。
    - 彈出棧頂元素。
  - 繼續這個過程，直到棧為空或者棧頂元素對應的值不再小于當前元素。
  - 最后，將當前下標 i % size 入棧。
返回結果:
- 返回結果數組 result，其中每個元素表示原數組 nums 中對應元素的下一個更大元素的值，若不存在則為 -1。

時間復雜度和空間復雜度

時間復雜度: O(n)，其中 n 是數組 nums 的長度。雖然代碼中遍歷了 2 * nums 的長度，但是每個元素至多被放入和彈出棧一次，因此總的時間復雜度為 O(n)。
空間復雜度: O(n)，需要一個大小為 n 的單調棧 st 和一個結果數組 result。

總結

這段代碼通過使用單調棧的策略，有效地解決了下一個更大元素 II 問題，能夠處理循環數組并找到每個元素的下一個更大元素的值。代碼邏輯清晰，通過兩次遍歷數組并使用模運算處理循環數組的特點，實現了高效的解題策略。單調棧在處理這類問題時表現出了強大的能力，能夠快速找到特定條件下下一個更大的元素，是解決此類問題的經典方法。在實際應用中，了解和掌握單調棧的使用方法對于解決與單調性相關的數組或序列問題具有重要意義。