JZTXT

算法随想Day52【单调栈】| LC503-下一个更大元素Ⅱ、LC42-接雨水

发布时间 2023-04-01 23:32:59作者: 冥紫将

LC503. 下一个更大元素Ⅱ

对于“每日温度”，相当于对nums数组，进行了两次遍历。用i % size所得余数作为下标，且循环的圈数为size * 2

vector<int> nextGreaterElements(vector<int>& nums)
{
    int size = nums.size();
    vector<int> result(size, -1);
    vector<int> sta;
    sta.push_back(0);
    for (int i = 1; i < size * 2; ++i)
    {   
        while (sta.empty() != true)
        {
            int temp = sta.back();
            if (nums[i % size] > nums[temp])
            {
                result[temp] = nums[i % size];
                sta.pop_back();
            }
            else
                break;
        }
        sta.push_back(i % size);
    }
    return result;
}

LC42. 接雨水

int trap(vector<int>& height)
{
    int sum = 0;
    stack<int> st;
    st.push(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()])
            {
                int 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;
}