挡板直方图问题 ：Leetcode 11 : Container With Most Water / Leetcode 42: Trapping Rain Water / Leetcode 84:Largest Rectangle in Histogram

1. Leetcode 11： Container With Most Water

Given n non-negative integers a₁, a₂, ..., a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

这一题大意是说： x 轴有很多垂直的线，代表高度，在这些线中选择两条线，使这两条线与x轴组成的容器的容积最大。
M1：  以每一个板子为一条边，遍历其他板子并记录容积，最后找到以当前板子为边的容器的容积最大值。最后会得到最大容积的两条边。 时间复杂度： O（n^2）
M2:  在M1的基础上考虑，其实在计算两个板子形成容器的容积时，如果其中某个板子为短板，那么以这个板子为一条边的容器的最大容积已经定了，那就是以这个为一条边，另一条边是离它最远的那个板子。如果用两个指针，left 和right，分别从0，size - 1处移动，每次只移动短板，在每次移动过程中，就能把以短板为一条边的容器的最大容积计算出来，最后当两个指针相遇时代表以所有板子为边的容器最大容积都求出来，并且可以得到最大容积。

挡板直方图容积问题， 有一个原理，短板原理，如果一个板子是短板，那么这个以这个板子为边的容器容积肯定不是最大，要找到最大的短板，需要移动指向短板的那个index，继续往后探索。

class Solution {
public:
//keep left_max and right_max
//compute the water in each index
//sum these water up
    int maxArea(vector<int>& height) {
        //sanity check
        if (height.size() == 0) return 0;
        int max1 = 0;
        int left = 0;
        int right = height.size()-1;
        while (left <= right) {
            max1 = max(max1, min(height[left],height[right]) * (right - left));
            if (height[left] < height[right]) {
                left = left + 1;
            }else {
                right = right - 1;
            }
        }
        return max1;
    }
};
time complexity: O(n)
space complexity: O(1)

2.  Leetcode Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

题目大意： 跟第一个挡板直方图问题类似，模型类似，但是这题是求所有这些挡板与X轴一起能积蓄多少水。
此题应用的挡板原理与第一题相同，短板原理，在这题中， 较短那块板子是不能够积水的，每次两个指针在移动的时候，只移动短板对应的指针，每次移动短板之前需要记录该短板能蓄水的容量。而对于较短的那块板子能蓄水的容量是该板子的左侧或者右侧的最大值 - 该板子的高度。

class Solution {
public:
    int trap(vector<int>& height) {
        //sanity check
        if (height.size() == 0) return 0;
        int left_max = 0;
        int right_max = 0;
        int left = 0;
        int right = height.size() - 1;
        int rst = 0;
        while (left <= right) {
            left_max = max(left_max, height[left]);
            right_max = max(right_max, height[right]);
            if (height[left] < height[right]) {
                rst += left_max - height[left];
                left = left + 1;
            } else {
                rst += right_max - height[right];
                right = right - 1;
            }
        }
        return rst;
    }
};
Time complexity: O(n)
Space complexity: O(1)

Leetcode 84:  Largest Rectangle in Histogram
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.