46. 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.

For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

参见ACM之家

思路一:
找到最高的index，分别计算它左右两边的部分，为什么要找到最高的index了，这是因为此时它是所有的高度重最高的，所有的都要以它作为标准

int trap(vector<int>& heights) {
        int maxHeight = 0, maxIndex;
        for (int i = 0; i < heights.size(); i++) {
            if (heights[i] > maxHeight) {
                maxHeight = heights[i];
                maxIndex = i;
            }
        }

        int sum = 0;
        maxHeight = 0;
        for (int i = 0; i < maxIndex; i++) {
            if (maxHeight > heights[i]) {
                sum += maxHeight - heights[i];
            }
            maxHeight = max(maxHeight, heights[i]);
        }

        maxHeight = 0;
        for (int i = heights.size() - 1; i > maxIndex; i--) {
            if (maxHeight > heights[i]) {
                sum += maxHeight - heights[i];
            }
            maxHeight = max(maxHeight, heights[i]);
        }

        return sum;

思路二:求出当前index出左右两边能够达到的最高高度，那么当前index能够积水的数量为min(left[index], right[index]) - height[index]

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> left(n , 0);
        vector<int> right(n , 0);
        int sum = 0;

        for(int i = 1; i < n; i++){
            left[i] = max(left[i - 1], height[i - 1]);
        }

        for(int i = n - 2; i >= 0; i--){
            right[i] = max(right[i + 1], height[i + 1]);
            int minHeight = min(left[i], right[i]);
            if(minHeight > height[i])
                sum += minHeight - height[i];
        }
        return sum;

    }
};

运用栈，栈维护的是一个不增的序列，当压入的元素比栈顶元素大时，就将所有小于等于此时要压入元素的所有栈中元素弹出，并计算相应的面积

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> st;
        //st.push(0);
        int sum = 0;
        for(int i = 0; i < height.size(); i++){
            if(!st.empty() && height[i] > height[st.top()]){

                int bottom = height[st.top()];
                st.pop();

                while(!st.empty() && height[i] >= height[st.top()]){
                    sum += (height[st.top()] - bottom)*(i -st.top() - 1);
                    bottom = height[st.top()];
                    st.pop();
                }
                if(!st.empty() && height[st.top()] > height[i])
                    sum += (height[i] - bottom)*(i -st.top() - 1);
            }
            st.push(i);
        }
        return sum;
    }
};