current position:Home>[algorithm hot] container with the most water

[algorithm hot] container with the most water

2022-06-24 09:55:18Tanyue Jianzhi Dachang

Container for the most water

Input :[1,8,6,2,5,4,8,3,7]
Output :49
explain : The vertical line in the figure represents the input array [1,8,6,2,5,4,8,3,7]. In this case , The container can hold water ( In blue ) The maximum value of is 49.

img

public class LC004_11_maxArea {
    

    public static void main(String[] args) {
    
        int[] ints = {
    1, 8, 6, 2, 5, 4, 8, 3, 7};
        System.out.println(maxArea(ints));
    }

    public static int maxArea(int[] height) {
    
        // Calculate every time 2 Volume of columns , Calculate the maximum   Double pointer + greedy 
        int left = 0, right = height.length - 1, ans = 0;
        while (left < right) {
    
            ans = height[left] < height[right] ?
                    Math.max(ans, (right - left) * height[left++]) :
                    Math.max(ans, (right - left) * height[right--]);
        }
        return ans;
    }
}

copyright notice
author[Tanyue Jianzhi Dachang],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/175/202206240834479927.html

Random recommended