496. 下一个更大元素 I
Note: 哈希+单调栈
503. 下一个更大元素 II
Note: 遍历一遍拼接数组（索引从0到2n - 1），索引需要模n（不用担心第二遍遍历时覆盖，因为覆盖的值和原值是一样的）。
42. 接雨水
Note: 两种做法，一种是两个数组维护每个位置上左侧的最高高度（记为maxLeft），和该位置右侧的最高高度（记为maxRight），那么由于短板效应，位置i上接的雨水就是min(maxLeft[i], maxRight[i]) - height[i]，上述两个数组可由dp做法得到，这一方法实际是按列加。
另一种做法是使用单调栈，栈中元素非递增（从栈底到栈顶），当进入栈的元素比栈顶元素（栈保存的是索引）指向的元素大，那么说明我们可能找到了一个凹槽，当前栈顶元素指向凹槽最低点，次栈顶元素指向凹槽左端点，待入栈元素指向凹槽右端点。
此时按照min(左端点高, 右端点高) - 最低点高来得到这个凹槽中心雨水的高度，另外通过计算右端点 - 左端点 - 1来得到凹槽中心雨水的宽度，宽度乘以高度即得到凹槽中的雨水数量，然后处理下一个凹槽（如果有），最后把所有凹槽的雨水数量相加得到总的接雨水数量。这里没有处理连续的同高度的柱子，因为这种情况下，左端点与最低点同高度的凹槽不会增加雨水数量（凹槽高度 = 左端点高 - 最低点高 = 0）。不过会增加一些无谓的计算，因此可以考虑特殊处理，但是代码会更麻烦点。这一方法实际上是按行加：
class Solution {
public:
int trap(vector<int>& height) {
// 双指针优化，通过左侧最高柱子与右侧最高柱子来算出每一列接的雨水
int n = height.size();
vector<int> maxLeft(n, 0);
for (int i = 1; i < n; ++i) {
maxLeft[i] = max(maxLeft[i - 1], height[i - 1]);
}
int sum = 0, cur, right = 0;
for (int i = n - 1; i >= 0; --i) {
cur = min(maxLeft[i], right) - height[i];
if (cur > 0) sum += cur;
right = max(right, height[i]);
}
return sum;
// 单调栈，求每个凹槽里的雨水总和，实际相当于每一行相加
int n = height.size();
stack<int> st;
st.push(0);
int ans = 0;
for (int i = 1; i < n; ++i) {
while (!st.empty() && height[i] > height[st.top()]) {
int mid = height[st.top()];
st.pop();
// 处理连续相同元素，忽略这些左端点=最低点的凹槽
while (!st.empty() && mid == height[st.top()]) st.pop();
if (!st.empty()) {
int h = min(height[i], height[st.top()]) - mid;
int w = i - st.top() - 1;
ans += h * w;
}
}
st.push(i);
}
return ans;
}
};
84. 柱状图中最大的矩形
Note: 和接雨水逆向，接雨水关注的是凹槽，本题关注的是凸起，一旦发生凸起，取凸起部分矩形面积的最大值（凸起柱子的高度×凸起区间宽度），由于可能出现顺序或者逆序数组，在这些情况下没有凸起导致不计算，因此在初始高度数组两端加入0，以避免不计算的情况。
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> st;
heights.insert(heights.begin(), 0);
heights.push_back(0);
st.push(0);
int n = heights.size(), ans = 0;
for (int i = 1; i < n; ++i) {
while (!st.empty() && heights[i] < heights[st.top()]) {
int mid = heights[st.top()];
st.pop();
if (!st.empty()) {
while (!st.empty() && mid == heights[st.top()]) st.pop();
int w = i - st.top() - 1;
ans = max(ans, w * mid);
}
}
st.push(i);
}
return ans;
}
};