[数据结构与算法]leetcode 42. 接雨水 (双指针，动态规划) c++ 2021-07-22

暴力解法

class Solution {
public:
    int trap(vector<int>& height) 
    {
        if (height.size() == 0)
            return 0;
        int sum = 0;
        for (int i = 1; i < height.size() - 1; i++)
        {
            int rheight = height[i];
            int lheight = height[i];
            for (int j = i + 1; j < height.size(); j++)
                if (height[j] > rheight)
                    rheight = height[j];
            for (int k = i - 1; k >= 0; k--)
                if (height[k] > lheight)
                    lheight = height[k];
            sum += min(lheight, rheight) - height[i];
        }
        return sum;
    }
};

优化一下，动态规划

class Solution {
public:
    int trap(vector<int>& height) 
    {

        int sum = 0;
        if (height.size() <= 2)
            return 0;
        vector<int> rheight(height.size(), 0);
        vector<int> lheight(height.size(), 0);

        lheight[0] = height[0];
        for (int i = 1; i < height.size() - 1; i++)
        {
            lheight[i] = max(lheight[i - 1], height[i]);
        }

        rheight[height.size() - 1] = height[height.size() - 1];
        for (int j = height.size() - 2; j >= 0; j--)
        {
            rheight[j] = max(rheight[j + 1], height[j]);
        }

        for (int k = 1; k < height.size() - 1; k++)
        {
            sum += min(lheight[k], rheight[k]) - height[k];
        }
        return sum;
    }
};

动态规划再优化一点空间

class Solution {
public:
    int trap(vector<int>& height) 
    {
        int sum = 0;
        if (height.size() <= 2)
            return 0;

        vector<int> rheight(height.size(), 0);
        rheight[height.size() - 1] = height[height.size() - 1];
        for (int j = height.size() - 2; j >= 0; j--)
        {
            rheight[j] = max(rheight[j + 1], height[j]);
        }
        
        int lheight = height[0];
        for (int k = 1; k < height.size() - 1; k++)
        {
            lheight = max(lheight, height[k]);
            sum += min(lheight, rheight[k]) - height[k];
        }
        return sum;
    }
};

双指针O(n) O(1)

class Solution {
public:
    int trap(vector<int>& height) 
    {
        int sum = 0;
        if (height.size() <= 2)
            return 0;
        int left = 0, right = height.size() - 1;
        int left_max = 0, right_max = 0;
        while (left < right)
        {
            if (height[left] < height[right])
            {
                if (height[left] >= left_max)
                    left_max = height[left];
                else
                    sum += left_max - height[left];
                left++;
            }
            else
            {
                if (height[right] >= right_max)
                    right_max = height[right];
                else
                    sum += right_max - height[right];
                right--;                
            }
        }
        return sum;
    }
};

单调栈

int trap(vector<int>& height)
{
    int ans = 0, current = 0;
    stack<int> st;
    while (current < height.size()) {
        while (!st.empty() && height[current] > height[st.top()]) {
            int top = st.top();
            st.pop();
            if (st.empty())
                break;
            int distance = current - st.top() - 1;
            int bounded_height = min(height[current], height[st.top()]) - height[top];
            ans += distance * bounded_height;
        }
        st.push(current++);
    }
    return ans;
}