題目
給定 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
解題
題目意思需要找到兩個點，使得容量最大 我們知道，能裝最大的水是由最矮的高度決定 假設i，k是結果 maxArea = Min(i, k) * (k - i)一、暴力解法
回圈每種可能性，記錄最大容量回傳，需要兩重回圈，所以時間復雜度：O(n * n)
public int MaxArea(int[] height) { if (height.Length <= 1) return 0; int max = 0; for (int i = 0; i < height.Length; i++) { for (int k = i + 1; k < height.Length; k++) { int area = System.Math.Min(height[i], height[k]) * (k - i); max = System.Math.Max(area, max); } } return max; }View Code
這個演算法真的很慢
二、雙向指標
設left = 0 , right = length - 1 計算容量
若left 比 right 矮（height[left] < height[right]) left++，反之 right--
我們知道容量有2個因素引起，高度 * 寬度，左邊指標移動或右邊移動都會減少寬度
只需要遍歷一次陣列，時間復雜度：O(n)
public int MaxArea(int[] height) { int maxArea = 0; for (int left = 0, right = height.Length - 1; left < right;) { int area = System.Math.Min(height[left], height[right]) * (right - left); maxArea = System.Math.Max(area, maxArea); if (height[left] < height[right]) left++; else right--; } return maxArea; }View Code
比演算法一快了10倍
附本文代碼：https://github.com/WilsonPan/Net.Algorithmic/tree/master/MaxArea
轉載請標明出處：https://www.cnblogs.com/WilsonPan/p/11840850.html
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/reverse-integer
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/127177.html
標籤：其他
上一篇：資料結構之鏈表-動圖演示