主題

LeetCode - 503. Next Greater Element II 解題心得

Not In My Back Yard | 2021-05-03 00:00:05 | 巴幣 0 | 人氣 31

題目連結:


題目意譯:
給定一個整數循環陣列 nums(即 nums[nums.length - 1] 的下一個元素為 nums[0]),回傳 nums 中每個元素的下一個較大數。

數字 x 的下一個較大數為第一個較大的數字位於其探訪順序之後的陣列元素,這意味著你可以循環地去找到其下一個較大數。如果不存在這樣子的數字,對於此數則回傳 -1。

限制:
1 ≦ nums.length ≦ 10 ^ 4
-10 ^ 9 ≦ nums[i] ≦ 10 ^ 9



範例測資:
範例 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]


解題思維:
類似這題這題,都是用一個堆疊(Stack)來為每個數字找到下一個較大數。

不過本題因為陣列是循環的(頭尾相連)。因此從左到右掃完之後,還要再從頭到尾掃過一次。而這次不需要將數字放入堆疊裡,只需判斷當前數字是否 > 堆疊頂端之條件。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作