双指针之接雨水问题

11. 盛最多水的容器

42. 接雨水

本篇文章来总结两个「接雨水」的问题！！

我一开始直接暴力，感觉方法很蠢！其实可以用双指针高效的解决这类问题，关于双指针相关内容可见 双指针技巧秒杀七道数组/链表题目

盛最多水的容器

题目详情可见 盛最多水的容器

定义两个指针，一个指向数组的开头，一个指向数组的结尾。如何移动指针才能使我们可以更加逼近最优解？？

当然是移动两个里面高度更小的指针

public int maxArea(int[] height) {
    int l = 0, r = height.length - 1;
    int ans = 0;
    while (l <= r) {
        int area = Math.min(height[l], height[r]) * (r - l);
        ans = Math.max(ans, area);
        if (height[l] < height[r]) l++;
        else r--;
    }
    return ans;
}

接雨水

题目详情可见 接雨水

这个题目也差不多，我们需要维护一个高度h，表示能使水不流走的最大高度！！

在使用双指针收缩区间的时候，不断的更新该高度h

xxxxxxxxxx
public int trap(int[] height) {
    int h = 0, ans = 0;
    int l = 0, r = height.length - 1;
    while (l <= r) {
        if (height[l] < height[r]) {
            h = Math.max(h, height[l]);
            ans += h - height[l];
            l++;
        } else {
            h = Math.max(h, height[r]);
            ans += h - height[r];
            r--;
        }
    }
    return ans;
}