LeetCode42/11 Trapping Rain Water/Container With Most Water/Hist area**

以你之姓@ 2022-08-07 11:42 10阅读 0赞

**一： 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`.

![rainwatertrap.png][]

地址：https://leetcode.com/problems/trapping-rain-water/

这道题关键点是是两边往中间遍历，记录当前第二高点secHeight，然后利用这个第二高点减去当前历经的柱子，剩下就装水容量了。  
为什么是第二高点？因为两边比较，最高的点不用动，只移动第二高点。(柱状图蓄水需要secHeight)

这也是阿里2015实习生招聘附加题第三题

class Solution {
    public:
        int trap(int A[], int n) {
            int secHeight = 0;
            int left = 0;
            int right = n-1;
            int area = 0;
            while(left < right){
                if(A[left] < A[right]){
                    secHeight = max(A[left], secHeight);    // 找到次最高点
                    area += secHeight - A[left];
                    left ++;
                }else{
                    secHeight = max(A[right], secHeight);
                    area += secHeight - A[right];
                    right --;
                }
                
            }
            return area;
            
        }
    };

**二：Container With Most Water**

题目：

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

Note: You may not slant the container.

链接：

https://leetcode.com/problems/container-with-most-water/

分析：此题和上一题很类似，上一题是柱子，这一题是线，求哪两根线之间的蓄水量最多，此题仍然是采用两边指针往中间遍历的思想，当height\[left\] < heght\[right\]，，只能left++(right--绝对会导致面积减小)，反之只能right--。(直线蓄水，双指针搞定！)

class Solution {
    public:
        int maxArea(vector<int> &height) {
            int left = 0, right = height.size()-1;
            //int secHeight = 0;
            int area = 0;
            while(left < right){
                if(height[left] < height[right]){    //  如果左边小于右边 只能对left++(因为right-- 只会更小)  并且求出此时面积与之前的对比
                    area = max(area,height[left]*(right - left));
                    left ++;
                }else{
                    area = max(area,height[right]*(right - left));   // 如果右边小于左边，只能对right--，并且求出此时面积与之前对比
                    right --;
                }
            }
            return area;
            
        }
    };

**三：(2015美团校招笔试题) 直方图的面积**

给定一个直方图，直方图用一个整数数组表示，直方图每列的宽度为1，求所给直方图所包含的最大矩形面积。举例，对于直方图\[2,7,8,4,1\], 它包含的最大矩形面积为7\*2=14，即被\[7,9\]完全包含的最大矩形。实现如下函数，参数hist表示直方图，n表示数组元素个数，返回包含最大矩形面积。

![Center][]

分析：这题首先得想到用暴力怎么求，暴力求法是以某个结点为中心，向两边扩展，求出以该结点为高度的矩形面积，然后求整体的全局最大值，这样的话，我们需要两个预处理数组，用来记录每个结点左边和右边第一个比它小的元素的下标。时间复杂度为O(n^2)， 空间复杂度为O(N)

代码如下：

// 暴力算法 O(N^2)    以某个结点向左向右扩展的面积，然后计算全局最大值。
    int max_contained_rect2(int *hist, int n){
    	int *pre_less = new int[n];    // 该结点向前能扩展到那个结点
    	int *post_less = new int[n];    // 该结点向后能扩展到那个结点
    
    	for(int i = 0; i < n; i++){    // 得到预处理数组，向前扩展找到比该结点小的结点，向后扩展找到比该结点大的结点
    		pre_less[i] = i;
    		post_less[i] = i;
    		int j = i-1;
    		while(j >= 0){
    			if(hist[j] < hist[i])break;    // 找到了小于的 break
    			pre_less[i] = j;
    			j--;
    		}
    		j = i+1;
    		while(j < n){
    			if(hist[j] < hist[i])break;
    			post_less[i] = j;
    			j++;
    		}
    	}
    	int result = 0;
    	for(int i = 0; i < n; i++){
    		result = max(result, (post_less[i]-pre_less[i]+1)*hist[i]);
    	}
    	delete []pre_less;
    	delete []post_less;
    	return result;
    }

方法二：当然此题的优化解法是O(N)，空间复杂度为O(N)，利用到一个栈，大于就压栈，压入的是数组元素对应的下标，小于等于就弹出栈结算。 空间复杂度为O(N)

int max_contained_rect(int *hist, int n){
    	if(n == 1) return hist[0];
    	if(n == 0) return 0;
    	stack<int> s;
    	s.push(-1);    // 可以将边界一起考虑进来
    	s.push(0);
    	int max_area = 0;
    	int i= 1;
    	while(i < n || s.top() != -1){     // s.top()!=-1主要用来处理剩余元素在栈中的情况
    		int top = s.top();
    		if(i < n && (top == -1 || hist[i] > hist[top])){
    			s.push(i);
    			i++;
    		}else{
    			s.pop();
    			max_area = max(max_area,(i-s.top()-1)*hist[top]);   // 面积为当前i减去栈顶值-1乘以高度
    		}
    	}
    
    	return max_area;
    
    }

[rainwatertrap.png]: http://www.leetcode.com/wp-content/uploads/2012/08/rainwatertrap.png
[Center]: /images/20220805/ec9cb09b46fa4a7a8fbc0f4c20e63a2d.png