一、題目大意
https://leetcode.cn/problems/next-greater-element-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
二、解題思路
我們可以用單調堆疊來解決這個問題，因為是回圈陣列，我們遍歷兩倍的陣列，然后對坐標i取余，取出數字，如果此時堆疊不為空，且堆疊頂元素小于當前數字，說明當前數字就是堆疊頂元素的右邊第一個較大的數，此時建立二者的映射并且去除當前堆疊頂元素，最后如果i小于n，則把i壓入堆疊，因為res的長度必須是n，超過n的部分我們只是為了給之前堆疊中的數字找較大值，所以不能壓入堆疊，
三、解題方法
3.1 Java實作
public class Solution {
public int[] nextGreaterElements(int[] nums) {
// 輸入: nums = [1,2,3,4,3]
// 輸出: [2,3,4,-1,4]
int n = nums.length;
int[] ans = new int[n];
Arrays.fill(ans, -1);
Stack<Integer> desStack = new Stack<>();
for (int i = 0; i < n * 2; i++) {
int num = nums[i % n];
while (!desStack.isEmpty() && nums[desStack.peek()] < num) {
ans[desStack.peek()] = num;
desStack.pop();
}
if (i < n) {
desStack.push(i);
}
}
for (int tmp : ans) {
System.out.print(tmp + ", ");
}
return ans;
}
}
四、總結小記
- 2022/8/22 今天適合穿短褲
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/502466.html
標籤：其他
上一篇：字典樹