【leetcode】42. 接雨水

题目内容

42. 接雨水

思路分析

本题的总体思路为从第二个柱子起，判断每个柱子左右两边柱子的最大高度，然后max(0, min(左右两边的最大高度)-当前柱子高度)即为当前柱子可以装的水量。

方法一：动态规划

参考资料（其中的解法3）

利用当前柱子及其左边所有柱子的最大高度max_left_height=max(当前柱子高度, 当前柱子左边一根的max_left_height)的特性，使用一个大小为n的数组保存所有max_left_height。

（对于右边也一样）

这样再遍历一遍所有柱子，用max(0, min(左右两边的最大高度)-当前柱子高度)即可算出每个柱子可以装的水量，最后全部相加即可得到总装水量。

方法二：动态规划 + 双指针

参考资料

初步尝试

很多动态规划都可以对其所用空间进行优化。方法一使用了两个大小为O(n)的数组max_left_heights和max_right_heights。因此考虑对这两个数组进行优化。

当尝试将数组用一个变量代替时，会遇到问题：按从左到右的顺序去遍历数组，max_left_height倒好说，一直记忆上一个最大值并做更新即可，而max_right_height不可以（因为压根就不知道右边什么情况）。

这时有一种巧妙的解决办法是使用双指针从左右两个方向进行遍历。

思想

规定left/right指向当前所要遍历的柱子，left_max和right_max为left以左的最大值和right以右的最大值。

                                   right_max
 left_max                             __
   __                                |  |
  |  |__   __??????????????????????  |  |
__|     |__|                       __|  |__
        left                      right

在某一时刻，对于left来说，left_max是可信的，而right_max是不可信的（因为不知道left到right中间的情况）。即left左边的最大值确定为left_max，右边的最大值大于等于right_max。因此，当left_max<=right_max时，可确定left处可以装的水为max(0, left_max-left)。即移动left，从左到右遍历。

（对于右边也一样）

代码

#include <vector>
#include <iostream>

using namespace std;

// 动态规划
// 时间复杂度O(n)
// 空间复杂度O(n)
class Solution1 {
public:
    int trap(vector<int>& height) {
        int n = height.size();

        if (n <= 2) return 0;
        
        int capacity{ 0 };
        // i左/右侧的最大高度
        vector<int> left_max_heights(n), right_max_heights(n);

        // 边界条件
        left_max_heights[0] = height[0]; 
        right_max_heights[n - 1] = height[n - 1];

        for (int i = 1; i <= n - 1; ++i) {
            // max(第i-1个左边的最大高度，第i个高度) -> 第i个左边的最大高度
            left_max_heights[i] = max(left_max_heights[i - 1], height[i]);
        }

        for (int i = n - 2; i >= 0; --i) {
            // max(第i-1个右边的最大高度，第i个高度) -> 第i个右边的最大高度
            right_max_heights[i] = max(right_max_heights[i + 1], height[i]);
        }

        for (int i = 1; i <= n - 1; ++i) {
            // 没有和0比较是因为left_max_heights/right_max_heights已经涵盖了当前柱
            // 子的大小
            capacity += min(left_max_heights[i], right_max_heights[i])
                - height[i]; 
        }

        return capacity;
    }
};

// 动态规划 + 双指针
// 时间复杂度O(n)
// 空间复杂度O(1)
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if (n <= 2) return 0;

        int left_max_height = height[0];
        int right_max_height = height[n - 1];
        int left = 1, right = n - 2;
        int capacity = 0;

        while (left <= right) {
            if(left_max_height <= right_max_height) {
                capacity += max(0, left_max_height - height[left]);
                left_max_height = max(left_max_height, height[left]);
                ++left;
            } else {
                capacity += max(0, right_max_height - height[right]);
                right_max_height = max(right_max_height, height[right]);
                --right;
            }
        }

        return capacity;


    }
};

int main() {
    Solution s;
    vector<int> input{ 0,1,0,2,1,0,1,3,2,1,2,1 };

    int output;
    output = s.trap(input);

    return output;
}

收获

掌握了“动态规划一般可以优化空间”的思想
终于解决了拖了很久的接雨水问题