11. Container with the most Water – LeetCode (leetcode-cn.com)

Share one of your own O(NLGN) methods.

When this problem saw really think to use double pointer to solve, including the official problem solution and a variety of other big guy to share are double pointer. But I found that when I think of double Pointers, unlike other double Pointers, at least a well-ordered array with double Pointers is passable. But as the elder brother joked, it is really a little difficult to prove the correctness of the double pointer, for the first time to do this problem is actually more difficult to think of.

Say what you think:

Essentially, we can solve this problem with two for loops, the outer for loop being the starting point, and the inner for loop being the ending point, and then see which side is smaller, and then multiply by the length. So for a certain endpoint, if the endpoint is a small endpoint, the point is to find a starting point that is farthest away from that endpoint and larger than that endpoint

For example, for the input [1,8,6,2,5,4,8,3,7], there is no number larger than 8 at the end of the second number, but for the third number,6, the number larger and farthest from it is 8. Similarly, for the last 7, the farthest and larger 8 is the second 8, not the third to last 8.

So the question boils down to this: For a number, how do you find the number that is farthest in front of it and larger than it?

So I borrowed the idea of “monotone stack” and used a list to maintain monotonically increasing sequences.

Loop through the number group, if the current number is larger than the top of the stack, it is directly pushed. If it’s smaller than the top of the stack, we go to the stack and find the first value that’s greater than or equal to that number. And this is the value that we said was in front of it, farthest away from it and larger than it.

The correctness of the algorithm is proved as follows:

First of all, follow our algorithm. The stack is a monotonously ascending sequence, so there must be a maximum number of numbers currently traversed in the stack. So, can there be a number that’s not on the stack but is larger than the current number?

Let’s say the stack is 1,3,8. If the next two numbers are 6, 2. For 6, the bigger thing is 8 on the stack. For 2, even though 6 is larger, 6 is not on the stack (because 6 is smaller than 8, it is not pushed). But we don’t really need to focus on 6. Because what’s in the stack is going to be bigger than that and come in earlier than that. For example, 8 is bigger than 6 and further away from 2, so we can just ignore 6.

Have to pass.

In implementation, we can represent this “stack” as a list, and since the list is monotonically ascending, we can use dichotomy to find the first value greater than or equal to the currently traversed number

Submit the first version of the algorithm with glee:

public int maxArea(int[] height) {
    List<Integer> stack = new ArrayList<>();

    int result = Integer.MIN_VALUE;
    for (int i = 0; i < height.length; i++) {
        if (stack.size() == 0 || height[i] > height[stack.get(stack.size() - 1)]) {
            stack.add(i);
        } else {

            int left = 0, right = stack.size() - 1;
            while (left < right) {
                int mid = (right - left) / 2 + left;
                if (height[stack.get(mid)] < height[i]) {
                    left = mid + 1;
                } else{ right = mid; } } result = Math.max(result, (i - stack.get(left)) * height[i] ); }}return result;
}
Copy the code

Yell an error.

The reason is not taken into account for monotonically ascending arrays. For example, the input [1,2,3,4,5] is integer.min_value

I thought about it, I just flipped the array over and called the comparison again. Interested students can also help optimize.

The last code submitted:

public int maxArea(int[] height) {

    int result = solve(height);

    List<Integer> list = Arrays.stream(height).boxed().collect(Collectors.toList());
    Collections.reverse(list);

    int[] height_ = list.stream().mapToInt(i -> i.intValue()).toArray();

    result = Math.max(result, solve(height_));
    return result;
}

private int solve(int[] height) {
    List<Integer> stack = new ArrayList<>();

    int result = Integer.MIN_VALUE;
    for (int i = 0; i < height.length; i++) {
        if (stack.size() == 0 || height[i] > height[stack.get(stack.size() - 1)]) {
            stack.add(i);
        } else {

            int left = 0, right = stack.size() - 1;
            while (left < right) {
                int mid = (right - left) / 2 + left;
                if (height[stack.get(mid)] < height[i]) {
                    left = mid + 1;
                } else{ right = mid; } } result = Math.max(result, (i - stack.get(left)) * height[i]); }}return result;
}
Copy the code

The effect is certainly not as good as O(n)…