今日的题目是503. 下一个更大元素 II和42. 接雨水
503下一个更大元素II 题目描述：
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
示例：
输入: nums = [1,2,1] 输出: [2,-1,2] 解释: 第一个 1 的下一个更大的数是 2； 数字 2 找不到下一个更大的数； 第二个 1 的下一个最大的数需要循环搜索，结果也是 2
我做这道题时的想法是如果如果遍历完一遍之后栈里面还有元素的话，就说明这些元素可能在循环数组中能够找到下一个比自身大的元素。
一开始写的时候是想要遍历完一遍后重新起一个for循环从栈顶元素的下标开始遍历遇到最后一个元素时将i重置为1，再接着遍历。
但仔细一想后，其实栈顶元素下标往后到数组最后一个元素其实在第一次for循环时就已经遍历过了。只需要重新起一个for循环从头开始遍历，直到遍历到栈顶元素本身还没有遇到目标元素，则说明没有更大的元素了。值得注意的是，一遇到比自身大的元素就需要break，不让后续的元素再更新到result数组中。
while(!st.empty()){
for (int i = 0; i < nums.size(); i++){
if (i == st.top()) break;
else if (nums[i] > nums[st.top()]){
result[st.top()] = nums[i];
break;
}
}
st.pop();
}Carl给出的方法是延长for循环中i遍历的长度至数组大小的两倍，当i大于数组的大小时，就对i取模，以实现循环数组。该方法在循环数组的场景都能使用。
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
stack<int> st;
vector<int> result(nums.size(), -1);
for (int i = 0; i < nums.size() * 2; i++){
while(!st.empty() && nums[i % nums.size()] > nums[st.top()]){
result[st.top()] = nums[i % nums.size()];
st.pop();
}
st.push(i % nums.size());
}
return result;
}
};整体的代码其实就是将每日温度那题代码中的i换成了i % nums.size()。
42 接雨水 题目描述：
给定 n 个非负整数表示每个宽度为 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 个单位的雨水（蓝色部分表示雨水）。
暴力（双指针）解法：
在for循环中遍历的i元素中，分别往左往右找到最大的元素。
for (int i = 0; i < height.size(); i++){
if (i == 0 || i == height.size() - 1) continue;
int rHeight = height[i];
int lHeight = height[i];
for (int r = i + 1; r < height.size(); r++){
rHeight = rHeight > height[r] ? rHeight : height[r];
}
for (int l = i - 1; l >= 0; l--){
lHeight = lHeight > height[l] ? lHeight : height[l];
}再将左右最大的元素中较小的元素减去当前遍历的heigh[i]，如果得出的高度h小于0，则说明该元素两边没有形成水槽。
int h = min(rHeight, lHeight) - height[i];
if (h > 0) result += h;可惜要遍历的元素太多每次都要将数组里的元素都遍历一遍，提交超时。
优化办法是一次性将每个元素左右分别最大的元素记录下来，就不用每次都遍历整个数组遍历个遍。
vector<int> maxLeft(height.size());
vector<int> maxRight(height.size());
maxLeft[0] = height[0];
for (int i = 1; i < height.size(); i++){
maxLeft[i] = max(height[i], maxLeft[i - 1]);
}
maxRight[height.size() - 1] = height[height.size() - 1];
for (int i = height.size() - 2; i >= 0; i--){
maxRight[i] = max(height[i], maxRight[i + 1]);
}遍历的过程比较像动态规划，需要上一个元素的值来决定这一个元素的值。
再同样的把左右最大的值中较小的元素减去height[i]即可得到结果。同样也是需要高度h大于0，才能证明该处有形成水槽。
int sum = 0;
for (int i = 0; i < height.size(); i++){
int h = min(maxLeft[i], maxRight[i]) - height[i];
if (h > 0) sum += h;
}
return sum;单调栈做法：
一开始做时想破脑袋都没想出怎么做，因为我总在想当前元素i与下一个元素的关系，我把水槽的左侧当做了当前元素来考虑，右边又有比自身小的元素，又有比自身大的元素，没法在单调栈中找到能够同时符合条件的做法，正确做法应该是将水槽底部当做当前元素来考虑，在单调递增栈中，右边较大的元素就是接下来要遍历的元素，会与栈顶的元素作比较，左边较大的元素就是单调递增栈中栈顶的下一个元素。需要注意的是单调栈做法是按行来求雨水的面积的，而暴力解法是按列来求的。
为了自己和他人的阅读方便，最好还是把当前元素与栈顶元素比较的小于、等于、大于三种结果分别写出。
因为要形成单调递增栈，height[i]<height[st.top()]时就将当前元素存入栈中。
if (height[i] < height[st.top()]) st.push(i);当height[i] == height[st.top()]时既可以存入也可以不存入，因为在后面的操作中，如果栈中有两个元素相等，需要左右左右两边分别大的元素取小来减去当前遍历元素i的话，得出的高度只会是0，所以此时存入栈中只会徒增计算量。
else if (height[i] == height[st.top()]){
st.pop();
st.push(i);
}有元素弹出栈的话，需要时刻注意不能够操作空栈，判断栈是否为空，因为单调栈方法是按行来计算雨水面积的，所以需要分别计算高度h，宽度w，再乘积之后加入到result中，记录栈顶元素为mid之后，弹出栈顶元素，此时栈顶元素就是mid元素的左边最大元素，当前遍历元素i就是mid元素的右边最大元素，两元素取小后减去mid元素即是mid元素的高，i减去st.top()即是mid元素的宽。最后要注意将当前元素入栈。
else{
while(!st.empty() && height[i] > height[st.top()]){
int mid = st.top();
st.pop();
if (!st.empty()){
int h = min(height[i], height[st.top()]) - height[mid];
int w = i - st.top() - 1;
result += h * w;
}
}
st.push(i);
}
