Container With Most Water (M)
題目
Given n non-negative integers \(a_1, a_2, ..., a_n\) , where each represents a point at coordinate \((i, a_i)\). n vertical lines are drawn such that the two endpoints of line i is at \((i, a_i)\) 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 and n is at least 2.
The above vertical lines are represented by array [1, 8, 6, 2, 5, 4, 8, 3, 7]. In this case, the max area of water (blue section) the container can contain is 49.
Example:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49
題意
給出n個坐標點 \((i, a_i)\) ，每個坐標點與點 \((i, 0)\) 構成一條直線，任選兩條直線，與x軸構成一個盛水的容器，求這個容器的最大容積，
思路
暴力法\(O(N^2)\)，
Two Pointers - \(O(N)\) : 設兩指標分別指向陣列的左右兩端，計算容積并更新最大容積，移動高度較短的指標進行下次回圈，證明：影響容器容積的因素有兩個，即底邊長度和較短邊高度，對于高度較短的一方，它已經達到了能夠構成的最大容積(因為底邊長度已經是最大)，只有更換較短邊才有可能抵消縮短底邊長度帶來的影響，
具體證明方法：過冰峰 - container-with-most-water(最大蓄水問題)
代碼實作
Java
class Solution {
public int maxArea(int[] height) {
int maxVolume = 0;
int i = 0, j = height.length - 1;
while (i < j) {
int volume = (j - i) * Math.min(height[i], height[j]);
maxVolume = Math.max(maxVolume, volume);
if (height[i] < height[j]) {
i++;
} else {
j--;
}
}
return maxVolume;
}
}
JavaScript
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function (height) {
let left = 0, right = height.length - 1
let max = 0
while (left < right) {
let h = Math.min(height[left], height[right])
max = Math.max(max, (right - left) * h)
if (h === height[left]) {
left++
} else {
right--
}
}
return max
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/43517.html
標籤：其他