题目1： 42. 接雨水
代码：

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size() <= 2) {
            return 0;
        }

        stack<int> stk;
        int result = 0;
        for(int i = 0; i < height.size(); i++) {
            if(stk.empty() || height[i] <= height[stk.top()]) {
                stk.push(i);
            }
            else {
                while(!stk.empty() && height[i] > height[stk.top()]) {
                    int bottom = stk.top();
                    stk.pop();
                    if(!stk.empty()) {
                        int h = min(height[i], height[stk.top()]) - height[bottom];
                        int w = i - stk.top() - 1;
                        result += w *h;
                    }
                }
                stk.push(i);
            }
        }
        return result;
    }
};

题目2：84. 柱状图中最大的矩形
代码：

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> left(n), right(n);
        stack<int> monoStk;

        for(int i = 0; i < heights.size(); i++) {
            while(!monoStk.empty() && heights[monoStk.top()] >= heights[i]) {
                monoStk.pop();
            }
            left[i] = monoStk.empty() ? -1 : monoStk.top();
            monoStk.push(i);
        }

        while(!monoStk.empty()) monoStk.pop();

        for(int i = n - 1; i >= 0; i--) {
            while(!monoStk.empty() && heights[monoStk.top()] >= heights[i]) {
                monoStk.pop();
            }
            right[i] = monoStk.empty() ? n : monoStk.top();
            monoStk.push(i);
        }

        int maxArea = 0;
        for(int i = 0; i < n; i++) {
            maxArea = max(maxArea, (right[i] - left[i] - 1) * heights[i]);
        }
        return maxArea;
    }
};