天津小程序网站开发公司小程序开发收费价目表

双指针法

• 思路：
  • 将数组前后设置为 left、right 指针，相互靠近；
  • 在逼近的过程中记录两端最大的值 leftMax、rightMax，作为容器的左右边界；
  • 更新指针规则：
    • 如果数组左边的值比右边的小，则更新 left 指针，同时累计当前组成的容器的容量；（该容器在更新 leftMax 时闭合）
    • 反之，则更新 right 指针，同理累计其组成容器的容量；

class Solution {
public:int trap(vector<int>& height) {int capacity = 0;int left = 0;int right = height.size() - 1;int leftMax = 0;int rightMax = 0;while (left < right) {leftMax = std::max(leftMax, height[left]);rightMax = std::max(rightMax, height[right]);if (height[left] < height[right]) {capacity += (leftMax - height[left]);++left;} else {capacity += (rightMax - height[right]);--right;}}return capacity;}
};