leetcode:Container With Most Water

题目

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

分析

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

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




是不能过.

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

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

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

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

将Maxarea更新,返回2

4:结束,返回最大面积




穷举

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

预测优化

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


双指针

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