leetcodeブラシテーマまとめメモ11

1095 ワード

leetcode11
Container With Most Water
 
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 line i is at (i, ai) 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. 両头から、まず面积を求めて、両侧の下标の差に両者の间の最低値、つまり短板を乗じて、それから遍歴を始めて、数値の小さい方は中へ行って、短板なので、自分で中へ行かなければならなくて、向こうの数値を小さい値にする数を见つけることができることを期待して、やっと最大の面积を得ることができて、それから面积を计算し続けて、前の面积と比べて、小さいものを置き換えて、遍歴を完了すればいいです.私の言語表現能力が弱いことを許してください.
class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0, r = height.size() - 1;
        int max = 0;
        
        while (l < r)
        {
            int temp = (r-l) * min(height[l], height[r]);
            if (temp > max)
            max = temp;
            
            if (height[l] <= height[r])
            l++;
            else
            r--;
        }
        
        return max;
    }
};