一隻箱子裡的貓,看著電腦螢幕

Schrödinger's Programmer

奔跑吧工程師,趁年輕跑得越遠越好

[LeetCode] #11 Container With Most Water (Medium)

LeetCode 第 11 題 Container With Most Water,難度 Medium

Ray

LeetCode #11 run result

用 PHP 解 LeetCode 系列,Container With Most Water,屬於 Medium

原始題目

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai).
n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0).
Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.

Example:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: 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.

Input: height = [1,1]
Output: 1

Input: height = [4,3,2,1,4]
Output: 16

Input: height = [1,2,1]
Output: 2

題目分析

  1. 輸入 height 是一串正整數,代表木板高度
  2. 找出中間面積最大的兩個數字(容納最多水)

解題過程

這題難在找出中間邏輯,運算本身並不難
使用雙指針這個方法,從頭尾向內夾找出最大值

第一指針 p1 理所當然就是陣列初始鍵值 0,第二指針 p2 則是陣列最後一個鍵值
又因為陣列鍵值是從 0 開始,所以是 陣列長度 - 1

使用 while 迴圈,因為鍵值交叉後算出來的結果會和先前重複,所以不需要計算
計算當前兩個指針之間的面積 $area,如果當前面積大於原先最大面積,則設定新最大面積

因為最大容量是用比較短的一端決定,且向內移動勢必讓寬度下降,若兩端高度不變則面積也會變小
所以比較兩個指針在陣列中的長度,長度較短的指針向中心移動
在這個邏輯下,若指針向內移動找到更長的一端,面積才有變大的可能!

class Solution {

    /**
     * @param Integer[] $height
     * @return Integer
     */
    function maxArea($height) {
        $p1 = 0;
        $p2 = count($height) - 1;
        $max_area = 0;
        while($p1 < $p2){
            $area = ($p2 - $p1) * min($height[$p1], $height[$p2]);
            if ($area > $max_area) {
                $max_area = $area;
            }
            if($height[$p1] < $height[$p2]) {
                $p1++;
            } else {
                $p2--;
            }
        }

        return $max_area;
    }
}

結果

result

最新文章

Category

Tag