LeetCode 739. 每日溫度
題目鏈接：https://leetcode.cn/problems/daily-temperatures/description/
文章鏈接：https://programmercarl.com/0739.%E6%AF%8F%E6%97%A5%E6%B8%A9%E5%BA%A6.html
思路
* 單調棧的本質是空間換時間，因為在遍歷的過程中需要用一個棧來記錄右邊第一個比當前元素高的元素，優點是整個數組只需要遍歷一次。* 單調棧里只需要存放元素的下標i就可以了，如果需要使用對應的元素，直接T[i]就可以獲取。* 單調棧的本質其實是記錄遍歷過的元素，單調棧的順序由棧頂到棧底是單調遞增的* 當我們遍歷的元素大于棧頂元素的時候，因為棧頂元素一定存放的是棧中最大的元素，則當前元素一定是第一個比棧頂元素大的元素。* 當我們遍歷的元素小于等于棧頂元素的時候，當前元素入棧
public int[] dailyTemperatures(int[] temperatures) {Stack<Integer> stack = new Stack<>();int[] res = new int[temperatures.length];stack.push(0);for (int i = 1; i < temperatures.length; 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;}
LeetCode 496.下一個更大元素 I
題目鏈接：https://leetcode.cn/problems/next-greater-element-i/description/
文章鏈接：https://programmercarl.com/0496.%E4%B8%8B%E4%B8%80%E4%B8%AA%E6%9B%B4%E5%A4%A7%E5%85%83%E7%B4%A0I.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
思路
本題思路同每日溫度一樣，都是利用單調棧來解體，唯一不同的是需要對Num1數組做一個映射。
public int[] nextGreaterElement(int[] nums1, int[] nums2) {Stack<Integer> stack = new Stack<>();HashMap<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums1.length; i++) {map.put(nums1[1], i);}stack.push(0);int[] res = new int[nums2.length];Arrays.fill(res, -1);for (int i = 1; i < nums2.length; i++) {if (nums2[i] <= nums2[stack.peek()]){stack.push(i);}else {while (!stack.isEmpty() && nums2[i] > nums2[stack.peek()]){res[map.get(stack.peek())] = i - stack.peek();stack.pop();}stack.push(i);}}return res;}
LeetCode 503.下一個更大元素II
題目鏈接：https://leetcode.cn/problems/next-greater-element-ii/description/
文章鏈接：https://programmercarl.com/0503.%E4%B8%8B%E4%B8%80%E4%B8%AA%E6%9B%B4%E5%A4%A7%E5%85%83%E7%B4%A0II.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
思路
本題思路同每日溫度一樣，都是利用單調棧來解體，不過數組是一個首尾相連的數組，我們只需要將兩個數組拼接即可
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;}
)
