一、LeetCode503. 下一個更大元素 II

題目鏈接：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

算法分析：

這道題跟739. 每日溫度差不多，只不過需要遍歷兩次nums，相當于將nums看成一個環。

代碼如下：

class Solution {public int[] nextGreaterElements(int[] nums) {int len = nums.length;Stack<Integer>st = new Stack<>();int[] answer = new int[len];//用來記錄nums中每個元素的下一個更大元素Arrays.fill(answer, -1);//用-1初始化for(int i = 0; i < len * 2; i++) {//遍歷兩次numswhile(!st.isEmpty() &&  nums[i % len] > nums[st.peek()]){answer[st.pop()] = nums[i % len];}st.push(i % len);}return answer;}
}

二、LeetCode42. 接雨水

題目鏈接：42. 接雨水

題目描述：

給定?n?個非負整數表示每個寬度為?1?的柱子的高度圖，計算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

輸入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
輸出：6
解釋：上面是由數組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下，可以接 6 個單位的雨水（藍色部分表示雨水）。 

示例 2：

輸入：height = [4,2,0,3,2,5]
輸出：9

提示：

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

算法分析：

用一張單調棧來存放沒有出現過下一個更高柱子的柱子高度，等出現高柱子時，就可以求出它與它前面第一個比它高或者相等的柱子之間所形成的凹槽面積。

代碼如下：

class Solution {public int trap(int[] height) {int len = height.length;int sum = 0;//用來記錄可接受的雨水體積Stack<Integer>st = new Stack<>();for(int i = 0; i < len; i++) {while(!st.isEmpty() && height[i] >= height[st.peek()]) {int mid = st.pop();//記錄凹槽的底部高度（不一定是兩邊之間最低的那一個）if(!st.isEmpty()) {int l = Math.min(height[i],height[st.peek()]) - height[mid];//兩邊的高度取最小值然后減去底部高度，就是可以增加的雨水高度int w = i - st.peek() - 1;//可以增加的雨水寬度sum += l * w;}}st.push(i);}return sum;}
}

總結：

第二題是比較難的！