題目描述
給定 n 個非負整數 a1，a2，...，an，每個數代表坐標中的一個點 (i, ai) ，在坐標內畫 n 條垂直線，垂直線 i 的兩個端點分別為 (i, ai) 和 (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
題目要求
int maxArea(int* height, int heightSize){ }
題解
1 int max(int a,int b){ 2 return a>b?a:b; 3 } 4 int min(int a,int b){ 5 return a<b?a:b; 6 } 7 8 int maxArea(int* height, int heightSize){ 9 int i=0,j=heightSize-1,count=0; 10 while(i<j){ 11 if(height[i]>height[j]){ 12 count=max(count,(j-i)*height[j]); 13 j--; 14 }else { 15 count=max(count,(j-i)*height[i]); 16 i++; 17 } 18 } 19 return count; 20 }
暴力解法可以通過但是耗時O(n^2)，此演算法僅耗時O(n)，值得學習參考，
初始狀態是兩個指標位于首尾，此時容器的底最大，接下來執行的操作是i++或者j--，無論選擇哪個，容器底都會減小，而容器的高度取決于短邊，因此為了獲取最大的容積，需要放棄短邊，也就是說，短邊的指標需要往內移動，保留了長邊以獲得更高邊的機會可能，
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/container-with-most-water
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/137171.html
標籤：其他