LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 动态规划，每个位置可以容纳的雨水量为，左右两侧最高高度的较小者减去该位置高度，如果左右两侧没有比该位置高的则容纳量为 0

class Solution {
 public:
  int trap(vector<int>& height) {
    int sz = size(height);
    vector<int> l(sz);
    vector<int> r(sz);
    for (int i = 1; i < sz; ++i) {
      l[i] = max(l[i - 1], height[i - 1]);  // height[i] 左侧最大高度
    }
    for (int i = sz - 2; i >= 0; --i) {
      r[i] = max(r[i + 1], height[i + 1]);  // height[i] 右侧最大高度
    }
    int res = 0;
    for (int i = 0; i < sz; i++) {
      res += max(0, min(l[i], r[i]) - height[i]);
    }
    return res;
  }
};

• 只用一个变量记录左右侧最高点中的较小值

class Solution {
 public:
  int trap(vector<int>& height) {
    int l = 0;
    int r = size(height) - 1;
    int mx = 0;
    int res = 0;
    while (l < r) {
      if (height[l] < height[r]) {
        mx = max(mx, height[l]);
        res += mx - height[l];
        ++l;
      } else {
        mx = max(mx, height[r]);
        res += mx - height[r];
        --r;
      }
    }
    return res;
  }
};