Shulou(Shulou.com)05/31 Report--

The editor of this article introduces in detail how C++ can hold the most water. The content is detailed, the steps are clear, and the details are handled properly. I hope that this article, "how to achieve the container with the most water in C++," can help you solve your doubts. Let's follow the editor's ideas slowly and deeply, together to learn new knowledge.

Container With Most Water's container with the 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 and nis at least 2.

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.

Example:

Input: [1,8,6,2,5,4,8,3,7]

Output: 49

The problem of finding the container with the most water is very similar to that Trapping Rain Water, but it is somewhat different. That question makes it possible to collect the amount of water that can be collected by Rain Water. This one only allows the largest one to hold water, and there is a difference that the edge of the container cannot be counted in it, but this problem can be counted. Comparatively speaking, this problem is easier. Here, you need to define that the I and j pointers point to the left and right ends of the array, and then the two pointers search in the middle, and each move calculates a value that is larger than the result. The algorithm for the amount of water in the container is to find the smaller of the left and right edges multiplied by the distance between the two edges. The code is as follows:

C++ solution one:

Class Solution {public: int maxArea (vector& height) {int res = 0, I = 0, j = height.size ()-1; while (I < j) {res = max (res, min (height [I], height [j]) * (j-I)); height [I] < height [j]? + I:-- j;} return res;}}

Java solution 1:

Public class Solution {public int maxArea (int [] height) {int res = 0, I = 0, j = height.length-1; while (I < j) {res = Math.max (res, Math.min (height [I], height [j]) * (j-I)); if (height [I] < height [j]) + + I; else-- j;} return res }}

It should be noted here that because the ternary operator A?B:C in Java must have a return value, you can only use if..else... To replace, I don't know why Java has such strict restrictions on ternary operators.

The following method makes a small optimization to the above method. For the same height, just move I and j directly, and no longer calculate the capacity. See the code below:

C++ solution 2:

Class Solution {public: int maxArea (vector& height) {int res = 0, I = 0, j = height.size ()-1; while (I < j) {int h = min (height [I], height [j]); res = max (res, h * (j-I)); while (I < j & h = = height [I]) + + I While (I < j & & h = = height [j])-- j;} return res;}}

Java solution II:

Public class Solution {public int maxArea (int [] height) {int res = 0, I = 0, j = height.length-1; while (I < j) {int h = Math.min (height [I], height [j]); res = Math.max (res, h * (j-I)); while (I < j & h = = height [I]) + + I While (I < j & & h = = height [j])-- j;} return res;}} here, the article "how to make C++ hold the most water container" has been introduced. If you want to master the knowledge of this article, you still need to practice and use it to understand it. If you want to know more related articles, please follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.