这三道题都是单调栈的应用
力扣739题 每日温度
使用单调栈主要有三个判断条件
1.当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
2.当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
3.当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
要保持单调递增的栈，如果栈头元素大于栈底元素，将栈顶元素弹出，此时result数组就可以进行记录了。
class Solution {
public:vector<int> dailyTemperatures(vector<int>& T) {// 递增栈stack<int> st;vector<int> result(T.size(), 0);st.push(0);for (int i = 1; i < T.size(); i++) {if (T[i] < T[st.top()]) { // 情况一st.push(i);} else if (T[i] == T[st.top()]) { // 情况二st.push(i);} else {while (!st.empty() && T[i] > T[st.top()]) { // 情况三result[st.top()] = i - st.top();st.pop();}st.push(i);}}return result;}
};力扣42题 接雨水
类型：单调栈
三种情况：
情况一：当前遍历的元素（柱子）高度小于栈顶元素的高度height[i]<height[st.top()]
情况二：当前遍历的元素（柱子）高度等于栈顶元素的高度height[i]==height[st.top()]
情况三：当前遍历的元素（柱子）高度大于栈顶元素的高度height[i]>height[st.top()]
先将下标0的柱子加入到栈中，st.push(0)，栈中存放我们遍历过的元素，因此先将下标0加进来。
然后从下标1开始遍历所有的柱子，for(int i=1;i<height.size();i++)
如果当前遍历的元素（柱子）高度小于栈顶元素的高度，就把这个元素加入栈中，因为栈中本来就要保持从小到大的顺序（从栈头到栈底）
需要维护单调递减的栈
class Solution {
public:int trap(vector<int>& height) {if (height.size() <= 2) return 0; // 可以不加stack<int> st; // 存着下标，计算的时候用下标对应的柱子高度st.push(0);int sum = 0;for (int i = 1; i < height.size(); i++) {if (height[i] < height[st.top()]) { // 情况一st.push(i);} if (height[i] == height[st.top()]) { // 情况二st.pop(); // 其实这一句可以不加，效果是一样的，但处理相同的情况的思路却变了。st.push(i);} else { // 情况三while (!st.empty() && height[i] > height[st.top()]) { // 注意这里是whileint mid = st.top();st.pop();if (!st.empty()) {int h = min(height[st.top()], height[i]) - height[mid];int w = i - st.top() - 1; // 注意减一，只求中间宽度sum += h * w;}}st.push(i);}}return sum;}
};
力扣84题 柱状图中最大的矩形1.情况一：当前遍历的元素heights[i]大于栈顶元素heights[st.top()]的情况
2.情况二：当前遍历的元素heights[i]等于栈顶元素heights[st.top()]的情况
3.情况三：当前遍历的元素heights[i]小于栈顶元素heights[st.top()]的情况
思路和接雨水差不多，除了栈内元素顺序和接雨水不同而已。
class Solution {
public:int largestRectangleArea(vector<int>& heights) {int result = 0;stack<int> st;heights.insert(heights.begin(), 0); // 数组头部加入元素0heights.push_back(0); // 数组尾部加入元素0st.push(0);// 第一个元素已经入栈，从下标1开始for (int i = 1; i < heights.size(); i++) {if (heights[i] > heights[st.top()]) { // 情况一st.push(i);} else if (heights[i] == heights[st.top()]) { // 情况二st.pop(); // 这个可以加，可以不加，效果一样，思路不同st.push(i);} else { // 情况三while (!st.empty() && heights[i] < heights[st.top()]) { // 注意是whileint mid = st.top();st.pop();if (!st.empty()) {int left = st.top();int right = i;int w = right - left - 1;int h = heights[mid];result = max(result, w * h);}}st.push(i);}}return result;}
};