LeetCode 503 下一个更大元素-ii 42接雨水 | 代码随想录25期训练营day58

单调栈2

LeetCode 503 下一个更大元素-ii 2023.12.22

• 题目链接
• 代码随想录讲解[链接]
  

vector<int> nextGreaterElements(vector<int>& nums) {
    //本题考虑了回环，回环的一种方法就是把数组=数组*2，
    //这样就形成了回环，本题就用该方法
    vector<int> nums1(nums.begin(), nums.end());
    nums.insert(nums.end(), nums1.begin(), nums1.end());
    vector<int> result(nums.size(), -1);
    stack<int> st;
    for (int i = 0; i < nums.size(); i++)
    {
        while (!st.empty() && nums[i] > nums[st.top()])
        {
            result[st.top()] =  nums[i];
            st.pop();
        }
        st.push(i);
    }
    //最后将result大小恢复到一半就是所求解
    result.resize(result.size()/2);
    return result;
}

LeetCode 42 接雨水 2023.12.22

• 题目链接
• 代码随想录讲解[链接]
  

int trap(vector<int>& height) {
    //双指针法
    //result变量存储最终雨水量
    /*
        int result = 0;
        //分别创建存储表，用于存储数组中每个元素左侧与右侧最大柱高
        vector<int> Lmax(height.size(), 0);
        vector<int> Rmax(height.size(), 0);
        //更新左侧最大柱高，初始化Lmax[0]
        Lmax[0] = height[0];
        for (int i = 1; i < height.size(); i++)
            Lmax[i] = max(height[i], Lmax[i-1]);
        //更新右侧最大柱高，初始化Lmax[height.size()-1]
        Rmax[height.size()-1] = height[height.size()-1];
        for (int i = height.size()-2; i >= 0; i--)
            Rmax[i] = max(height[i], Rmax[i+1]);
        //计算每个处于中间较低柱子上的水量，并更新总水量到result
        for (int i = 0; i < height.size(); i++)
        {
            int deltaheight = min(Lmax[i], Rmax[i]) - height[i];
            if(deltaheight > 0)
                result += deltaheight;
        }
        return result;
        */

    //单调栈法
    //result变量存储最终雨水量
    int result = 0;
    //创建单调栈存储已经遍历过的元素的索引，且该栈元素呈单调递增
    stack<int> st;
    for (int i = 0; i < height.size(); i++)
    {
        //当栈不空且当前柱高大于栈顶索引对应的柱高
        while (!st.empty() && height[i] > height[st.top()])
        {
            //用mid变量存储栈顶的索引
            int mid = st.top();
            //栈顶索引出栈
            st.pop();
            //如果栈还不空，那么此时栈顶索引对应柱高也大于mid索引对应柱高，
            //height[st.top()]>height[mid], height[i] > height[mid]
            if(!st.empty())
            {
                //计算水柱高
                int h = min(height[st.top()], height[i]) - height[mid];
                //计算水柱宽
                int l = i - st.top() - 1;
                //更新所有水量
                result += l*h;
            }
        }
        //入栈
        st.push(i);
    }
    return result;
}