Leetcode 42

Link: https://leetcode.cn/problems/trapping-rain-water/

题目要求

给定一个height数组，每个元素表示柱子的高度，求这个柱子序列能盛的雨水量

核心算法和原理

转换一下题意：对于每个元素h[i]，求在其之前（包括自己）与之后（包括自己）的元素最大值中的最小值m，求Σ m - h[i]

关键：维护每个元素的最小和最大值

朴素做法：正反各遍历一遍，维护每个元素的frontMax和backMax，然后再计算

时间复杂度O(n)，空间复杂度O(n)

双指针做法：首尾设置双指针，只维护一个M_frontMax和M_backMax，若M_frontMax < M_backMax则计算左指针所在元素的「可承接雨水量」(m - h[i])，左指针右移，直至两个指针相遇；反之

原理：对于左指针i，M_frontMax一定是i对应的frontMax，但是M_backMax不一定是，但是一定≤i对应的backMax；当M_frontMax < M_backMax时，有i的frontMax < M_backMax ≤ i的backMax，所以i的「可承接雨水量」可被计算，然后更新i和frontMax继续重复算法
时间复杂度O(n)，空间复杂度O(1)

单调栈做法（还没研究）

代码


// 双指针
class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        int left = 0, right = height.size() - 1;
        int pre_max = 0, suf_max = 0;
        while (left < right) {
            pre_max = max(pre_max, height[left]);
            suf_max = max(suf_max, height[right]);
            // 谁小移动谁：保证此次ans累加的值是正确的，即left对应的pre_max一定小于suf_max（或left本身就对应pre_max），
            ans += pre_max < suf_max ? pre_max - height[left++] : suf_max - height[right--];
        }
        return ans;
    }
};