现在的位置: 首页 > 综合 > 正文

leetcode:Container With Most Water

2019年11月04日 ⁄ 综合 ⁄ 共 1253字 ⁄ 字号 评论关闭
  1. 题目

    给定一系列整数代表在0,1,2,3...坐标点板的高度,求出在任意两个板之间能装水的最大截面积.

  1. 分析

       首先,我们会想到遍历下每一个板,选取任意两个板,求出最大的,但是这个会超时,效率太低

      

 其次,我们乐意想到在遍历的基础上优化,即有一个预测,这样可以在一定程度上提高效率,但是并不是太好,我试了下还


不能过.

    

 我们就要想,能不能遍历一遍就求出来.

    

    1:left = 0, right =height.size();

    

    2:如果left< right,3,否则四

   

   3:求出此时面积的大小,并判断左边和右边板的高度哪一个大,左边小于右边的话,left++;否则,right--;并判断是否
 

Maxarea更新,返回2

   

   4:结束,返回最大面积


  穷举

class Solution {
public:
    int maxArea(vector<int> &height) {
        int area,Maxarea,high;
        Maxarea = 0;
        for(int i=0;i<height.size();i++){
        	if(height[i]==0) continue;
        	for(int j=0;j<i;j++){
        		area = (i-j)*(high=height[i]>height[j]? height[j]:height[i]);
        		if(area>Maxarea)
        			Maxarea = area;
        	}
        }
        return Maxarea;
    }
};

  预测优化

class Solution {
public:
    int maxArea(vector<int> &height) {
        int area,Maxarea,high;
        Maxarea = 0;
        for(int i=0;i<height.size();i++){
        	if(height[i]==0) continue;
        	int steplen = i - Maxarea/height[i];
        	for(int j=0;j<i&&j<=steplen;j++){
        		area = (i-j)*(high=height[i]>height[j]? height[j]:height[i]);
        		if(area>Maxarea)
        			Maxarea = area;
        	}
        }
        return Maxarea;
    }
};

   双指针

class Solution {
public:
    int maxArea(vector<int> &height) {
        int left = 0;
        int right = height.size() - 1;
        int area,Maxarea,high,step;
        Maxarea = 0;
        int flag;
        while(left<right){
        	area = (right-left)*(high=height[left]>height[right]? height[right]:height[left]);
        	if(height[left]<height[right])
        		left++;
        	else
        	    right--;        	
        	if(area>Maxarea)
        		Maxarea = area;
        }
        return Maxarea;
    }
};

抱歉!评论已关闭.