- 503.下一个更大元素II
与496.下一个更大元素 I的不同是要循环地搜索元素的下一个更大的数。那么主要是对于遍历结束后，单调栈里面剩下的那些元素。
如果直接把两个数组拼接在一起，然后使用单调栈求下一个最大值就可以。
代码实现的话，不用直接把数组后面再接一个数组，而是单调栈走2遍这个数组即可。
代码如下。第二次遍历使用取余的方法。
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n=nums.size();
vector<int> result(n,-1);
stack<int> st;
for(int i=0;i<2*n;++i){
int k=i%n;
while(!st.empty() && nums[k]>nums[st.top()]){
result[st.top()]=nums[k];
st.pop();
}
st.push(k);
}
return result;
}
};- 42. 接雨水
依据列来计算更好理解，能引入单调栈：可以看出，因为左侧最高柱子和右侧最高柱子肯定不会存储雨水（左侧和右侧包含自己，因为自己是一侧最高的话不会存储雨水），所以每一列雨水的高度，取决于，该列 左侧最高的柱子和右侧最高的柱子中最矮的那个柱子的高度。
下面图片以柱子4为例，可以看见中间所有柱子都满足这个结论，最两边的柱子不会存储雨水。
转化问题后，有3种办法解决：
- 会超时的暴力解法。
- 双指针优化。
- 重点的单调栈。
1、暴力解法。
对于每个元素，都从左、从右找最大高度的柱子lheight、rheight，所以外层循环是0到n-1，内层循环从i往左，然后从i往右找最大高度的柱子lheight、rheight，最多会查找n次。所以时间复杂度是O(n^2)，空间复杂度O(1)。但是会超时。
2、双指针优化。
当前元素的左边、右边最大高度的柱子lheight、rheight其实跟前一个元素的lheight、rheight有关。注意左边最大和右边最大要把自己考虑进去，如果不包含，左边最大/右边最大的可能比自己还小，那么相减是负数，最终结果比正确结果小。
当前i的lheight取决于左边i-1的lheight，rheight取决于右边i+1的rheight。具体如下：
当前i的lheight=max(前一个lheight，height[i])，所以需要从左到右得到lheight。
那么参照lheight，当前i的rheight应该=max(后一个lheight，height[i])，与上面相反，从右到左得到。
根据这个过程先把所有元素的lheight数组和rheight数组求出来，然后再遍历元素的时候，直接就是min(lheight[i],rheight[i])-height[i]。时间复杂度是O(n)，空间复杂度O(n)。
代码如下。
class Solution {
public:
int trap(vector<int>& height) {
int n=height.size();
int l1,r1,l2,r2;
int count=0;
vector<int> lheight(n);
vector<int> rheight(n);
//初始化
lheight[0]=height[0];
rheight[n-1]=height[n-1];
for(int i=1;i<n-1;++i){//中间元素的lheight和rheight
lheight[i]=max(lheight[i-1],height[i]);
rheight[i]=max(rheight[i+1],height[i]);
}
for(int i=n-2;i>0;--i){
rheight[i]=max(rheight[i+1],height[i]);
}
for(int i=0;i<n;++i){
if(i==0 || i==n-1)continue;
int cur=min(lheight[i],rheight[i])-height[i];
count+=cur;
}
return count;
}
};上面的1、2都是按照列的方式去装水，因为是找左右两边最大元素。
3、单调栈
如果按行装水的话，就可以通过下一个更大元素和上一个最大元素来求。
以上图为例，下标2左边更大是1，右边更大是2，所以自己这行（以下标2柱高0为底，以min(左边更大值，右边更大值)为高，宽度是2个更大值的距离1）可以存储1的雨水；下标4左边更大是2，右边更大是3，所以自己这行（以下标4柱高1为底，以min(左边更大值，右边更大值)=2为高，宽度是2个更大值的距离3）可以存储3的雨水……左边更大和右边更大有1个不存在的则存储雨水为0。
所以要用单调栈计算出上一个更大值和下一个更大值的下标leftmax和rightmax。然后i柱子处可以存储的雨水是：(min(height[leftmax],height[rightmax])-height[i])*(rightmax-leftmax-1)。
怎么计算上一个更大值和下一个更大值呢？还想着2次单调栈，实际上，1次单调栈即可。采用单调递增栈，在元素 i 比栈顶大的情况下，如果栈顶同时也比次栈顶要小，这个时候就出现一个凹槽，也就找到了上一个更大值（次栈顶）和下一个更大值（元素i）。所以这个单调递增栈，必须是严格的单增，这个凹槽一定是次栈顶>栈顶<比栈顶大的元素i。
所以如果元素i==栈顶的话，要么不操作，要么替换这个栈顶，才能满足单调栈。这里需要选择的操作是替换栈顶，因为我们要求宽度的时候 如果遇到相同高度的柱子，需要使用最右边的柱子来计算宽度。
如果<栈顶，就直接入栈。
清晰说明了3种情况：
class Solution {
public:
int trap(vector<int>& height) {
int n=height.size();
int count=0;
stack<int> st;
st.push(0);
for(int i=1;i<n;++i){
if(height[i]==height[st.top()]){
st.pop();
st.push(i);
}
else if(height[i]<height[st.top()])st.push(i);
else{
while(!st.empty()&&height[i]>height[st.top()]){//有凹槽,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;//宽
count+=w*h;
}
}
st.push(i);
}
}
return count;
}
};相等的情况pop()之前应该检查是否为空，但是初始和每一次循环结尾都有入栈操作，所以这里不用加。
简化。简化后的3个pop()操作都有可能遇栈空，所以都要加条件，否则报错：
class Solution {
public:
int trap(vector<int>& height) {
int n=height.size();
int count=0;
stack<int> st;
st.push(0);
for(int i=1;i<n;++i){
while(!st.empty()&&height[i]>height[st.top()]){//有凹槽,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;//宽
count+=w*h;
}
}
if(!st.empty()&&height[i]==height[st.top()]){
st.pop();
}
st.push(i);
}
return count;
}
};
