【数据结构与算法】之容器盛最多水的算法实现

一、题目要求

• 给你 n 个非负整数 a₁，a₂，…，a_n，每个数代表坐标中的一个点 (i, a_i) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, a_i) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
• 说明：不能倾斜容器，且 n 的值至少为 2。

• 图中垂直线代表输入数组 [1, 8, 6, 2, 5, 4, 8, 3, 7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
• 示例

	输入：[1,8,6,2,5,4,8,3,7]
	输出：49

  

 

  
1
  
2
 

二、求解算法

• Siwft 示例：
  • 通过题意，盛水的高度是由区间左右的最小值决定，而容纳水的体积是由高度和宽度公共决定。 因此，我们区间两边不断的缩进，求出每一个区间 题解，并记录其中最大的即可。
  • 初始状态选择最左最右的柱子，然后矮柱子往中间挪动。每一步操作，都求出能容纳的水的体积。
  • Swift 算法如下：

	class Solution {
	    func maxArea(_ height: [Int]) -> Int {
	      
	      var left = 0
	      var right = height.count-1
	      var maxAns = 0
	      var per = 0
	    
	      while left < right {
	        per = min(height[left], height[right]) * (right-left)
	        maxAns = max(maxAns, per)
	        if height[left] <= height[right] {
	          // 优先剔除矮木板
	          left += 1
	        } else {
	          right -= 1
	        }
	      }
	      return maxAns
	    }
	}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
 

• Java 示例：
  • 算法流程： 设置双指针 i，j 分别位于容器壁两端，根据规则移动指针（后续说明），并且更新面积最大值 res，直到 i == j 时返回 res。
  • 指针移动规则与证明： 每次选定围成水槽两板高度 h[i]，h[j] 中的短板，向中间收窄 1 格。以下证明：
    • 设每一状态下水槽面积为 S(i,j),(0 <= i < j < n)，由于水槽的实际高度由两板中的短板决定，则可得面积公式 S(i,j) = min(h[i],h[j]) × (j−i)。
    • 在每一个状态下，无论长板或短板收窄 1 格，都会导致水槽底边宽度 −1：
      • 若向内移动短板，水槽的短板 min(h[i],h[j]) 可能变大，因此水槽面积 S(i,j) 可能增大。
      • 若向内移动长板，水槽的短板 min(h[i],h[j]) 不变或变小，下个水槽的面积一定小于当前水槽面积。
  • 因此，向内收窄短板可以获取面积最大值。换个角度理解：
    • 若不指定移动规则，所有移动出现的 S(i,j) 的状态数为 C(n,2)，即暴力枚举出所有状态。
    • 在状态 S(i,j) 下向内移动短板至 S(i+1,j)（假设 h[i]<h[j] ），则相当于消去了 S(i,j−1),S(i,j−2),…,S(i,i+1) 状态集合。而所有消去状态的面积一定 <=S(i,j)：
      • 短板高度：相比 S(i,j) 相同或更短（<=h[i]）；
      • 底边宽度：相比 S(i,j) 更短。
    • 因此所有消去的状态的面积都 <S(i,j)。通俗的讲，我们每次向内移动短板，所有的消去状态都不会导致丢失面积最大值 。
  • 复杂度分析：
    • 时间复杂度 O(N)，双指针遍历一次底边宽度 N 。
    • 空间复杂度 O(1)，指针使用常数额外空间。
  • Java 算法如下：

	class Solution {
	    public int maxArea(int[] height) {
	        int i = 0, j = height.length - 1, res = 0;
	        while(i < j){
	            res = height[i] < height[j] ? 
	                Math.max(res, (j - i) * height[i++]): 
	                Math.max(res, (j - i) * height[j--]); 
	        }
	        return res;
	    }
	}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
 

文章来源: blog.csdn.net，作者：Serendipity·y，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/Forever_wj/article/details/108715016