Leetcode 739.42. 每日温度 接雨水 单调栈 C++实现

问题：Leetcode 739. 每日温度

算法1：从右到左

        栈中记录下一个更大元素的「候选项」。

代码：

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> ans(n); // 初始化返回数组为0
        stack<int> st; // 栈
        for(int i = n - 1;i >= 0;i--) {
            int t = temperatures[i];
            while(!st.empty() && t >= temperatures[st.top()])   st.pop(); // 说明栈顶元素不符合条件，出栈
            if(!st.empty()) ans[i] = st.top() - i;
            st.push(i); // 当前温度进栈
        }
        return ans;
    }
};

算法2：从左到右

        栈中记录还没算出「下一个更大元素」的那些数（的下标）。

代码：

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> ans(n); // 初始化返回数组为0
        stack<int> st; // 栈
        for(int i = 0;i < n;i++){
            int t = temperatures[i];
            while(!st.empty() && t > temperatures[st.top()]){
                ans[st.top()] = i - st.top();
                st.pop();
            }
            st.push(i);
        }
        return ans;
    }
};

问题：Leetcode 42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

算法：前两种算法请看文章Leetcode 11.42. 接雨水

        在这里运用单调栈的方法解决。从左向右遍历，一步步填坑，如果右边界大于等于栈中的值，则可以填，填完后先将填完的位置出栈，然后把当前遍历到的位置入栈。

代码：

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        stack<int> st;
        for(int i = 0;i < height.size();i++){
            while(!st.empty() && height[i] >= height[st.top()]){
                int bottom_h = height[st.top()]; // 要填的位置的高
                st.pop();
                if(st.empty())    break; // 如果左边界不存在，break
                int left = st.top(); // 要填的位置的左边界序号
                int dh = min(height[left],height[i]) - bottom_h; // 要填的高
                ans += dh * (i - left - 1);
            }
            st.push(i);
        }
        return ans;
    }
};