LeetCode 42 接雨水 题解

题目描述：

基本想法：

对于每个方格索引 \(x\)，其容量\(c(x)\)取决于其左边最高的格子和右边最高的格子，也就是说令：

\[t(x) = \min(\max_{y<x}{\{h(y)\}} , \max_{y>x}{\{h(y)\}})\]

则

\[ c(x) = \begin{cases} t(x) - h(x), & \text{if } y > x \\ 0, & \text{otherwise} \end{cases} \]

故我们可以有代码：

class Solution {
public:
  int trap(vector<int> &height) {
    int n = height.size();
    int *maxLessThan = new int[n];
    int *maxGreaterThan = new int[n];
    maxLessThan[0] = 0;
    maxGreaterThan[n - 1] = 0;

    int curMax = 0;
    for (int i = 1; i < n; ++i) {
      if (height[i - 1] > curMax)
        curMax = height[i - 1];
      maxLessThan[i] = curMax;
    }
    curMax = 0;
    for (int i = n - 2; i >= 0; --i) {
      if (height[i + 1] > curMax)
        curMax = height[i + 1];
      maxGreaterThan[i] = curMax;
    }

    int ret = 0;
    for (int i = 0; i < n; ++i) {
      int t = std::min(maxLessThan[i], maxGreaterThan[i]);
      int capa = t > height[i] ? t - height[i] : 0;
      ret += capa;
    }

    return ret;
  }
};

当然还有同样思想的双指针法，此处不表。