每日一题 | 42接雨水 和 1218最长定差子序列


42. 接雨水(I、II。掌握这种思想)


思路:暴力(超时)
  1. 能接到的雨水总量 sum,是每一列雨水 f(i)的和
  2. f(i)又是每一列最多能接的雨水capable, 与 该列的柱子高度 height[i] 的差
  3. capable根据短板效应,属于 i 左边的最大值lheight 与 右边的最大值 rheight 的最小值

所以综合一下得到 sum( min(lheght, rheight) - height[i] ) (1 < i < height.size()-1)

每日一题 | 42接雨水 和 1218最长定差子序列

class Solution {
public:
    int trap(vector<int>& height) {
        int sum = 0;
        // 遍历每一列
        for(int i = 0; i < height.size(); i++) {
            // 跳过第一列和最后一列
            if(i == 0 || i == height.size()-1) continue;
            // 用两个变量分别记录左右两侧的最大值
            int lheight = 0;
            int rheight = 0;
            // 求左侧最大值
            for(int j = 0; j < i; j++) {
                if(height[j] > lheight) lheight = height[j];
            }
            // 求右侧最大值
            for(int j = i+1; j < height.size(); j++) {
                if(height[j] > rheight) rheight = height[j];
            }
            // 得到当前i列能接到的雨水
            int cur = min(lheight, rheight) - height[i];
            // 累加到sum中
            if(cur > 0) sum += cur;
        }
        return sum;
    }
};

思路:动态规划

与上种解法有所不同,此处利用两个 vector 容器记录对应每个 i 值的 lheight 和 rheight ,最后累积相加即可。

class Solution {
public:
    int trap(vector<int>& height) {
        // 处理边界
        if(height.size() <= 2) return 0;
        // 两个维护左右侧最大柱高的容器
        vector<int> lmax(height.size(), 0);
        vector<int> rmax(height.size(), 0);
        int len = rmax.size();
		
        // 先遍历一次记录左侧最大柱高的容器
        lmax[0] = height[0];
        for(int i = 1; i < len; i++) {
            lmax[i] = max(height[i], lmax[i-1]);
        }
		
        // 先遍历一次记录右侧最大柱高的容器
        rmax[len - 1] = height[len - 1];
        for(int i = len-2; i >= 0; i--) {
            rmax[i] = max(height[i], rmax[i+1]);
        }
        
        // 遍历全部,累计相加
        int sum = 0;
        for(int i = 0; i < len; i++) {
            int cur = min(lmax[i], rmax[i]) - height[i];
            if(cur > 0) sum += cur;
        }

        return sum;
    }
};
  • 76.05%
  • 11.97%


1218. 最长定差子序列(这题很绝,代码短而精)


思路:动态规划

参考了官方题解,解法非常巧妙。首先利用了动态规划的思想,从左往右遍历整个数组,并建立一个辅助数组v。

  • 当遍历到 i 时,就根据 v[i - difference]的内容来更新v[i]的值。

arr = [ 1,2,4,3,5,8,7,5,1 ],difference = 2 可以手动测试一下,就知道这一句话实现了什么内容

class Solution {
public:
    int longestSubsequence(vector<int> &arr, int difference) {
        int res = 0;
        // 此处辅助数组的建立要多加注意!
        unordered_map<int, int> map;
        for(auto i : arr) {
            map[i] = map[i-difference] + 1;
            res = max(res, map[i]);
        }
        return res;
    }
};
  • 88.68%
  • 52.83%

关于辅助数组的建立:

由于上述代码的关键句会涉及到访问未初始化的数组成员,因此如果用:vector<int> v来接收和计算此题,一定会报错!

而 map 使用 [] 符号取值时,当 key 不存在时,c++ 会利用该 key 及默认构造的 value,组成一个{key, value}对,插入 map 中,即将该 key 对应的 value 初始化为 0,所以访问不存在的元素时不会出错。


上一篇:力扣:42. 接雨水


下一篇:每日一题:42. 接雨水