1130. Minimum Cost Tree From Leaf Values

T: O(n^2), every round finds the smallest index(from n numbers), then count pre, post, and do n times. so n^2

S: O(n), removeElement needs n space to copy

```java
class Solution {
    public int mctFromLeafValues(int[] A) {
        int res = 0;
        while (A.length > 1) {
            int i = indexOfMin(A);
            if (i == A.length-1) {
                res += A[i-1] * A[i];
            } else if (i == 0) {
                res += A[i+1] * A[i];
            } else {
                res += Math.min(A[i-1], A[i+1]) * A[i];
            }
            A = removeElement(A, i);
        }
        return res;
    }

    public int indexOfMin(int[] A) {
        int minIndex = 0;
        for (int i = 1; i < A.length; i++) {
            if (A[i] < A[minIndex]) {
                minIndex = i;
            }
        }
        return minIndex;
    }

    public int[] removeElement(int[] A, int index) {
        int[] newArray = new int[A.length - 1];
        System.arraycopy(A, 0, newArray, 0, index);
        System.arraycopy(A, index + 1, newArray, index, A.length - index - 1);
        return newArray;
    }
}
```

Mono Stack

T: O(n)

S: O(n)

```java
class Solution {
    public int mctFromLeafValues(int[] arr) {
        int[] nextGreater = nextGreater(arr);
        int[] prevGreater = prevGreater(arr);

        int result = 0;
        for (int i = 0; i < arr.length; i++) {
            // if nextGreater and prevGreater are both Integer.MAX_VALUE which means no need to cal, means this number is the biggest in the array
            if (nextGreater[i] != Integer.MAX_VALUE || prevGreater[i] != Integer.MAX_VALUE) {
                result += arr[i]*Math.min(nextGreater[i], prevGreater[i]);
            }
        }
        return result;
    }
    private int[] nextGreater(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        Arrays.fill(result, Integer.MAX_VALUE);
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && arr[i] >= arr[stack.peek()]) {
                result[stack.pop()] = arr[i];
            }
            stack.push(i);
        }
        return result;
    }
    private int[] prevGreater(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        Arrays.fill(result, Integer.MAX_VALUE);
        Stack<Integer> stack = new Stack<>();
        for (int i = n-1; i >= 0; i--) {
            while (!stack.isEmpty() && arr[i] > arr[stack.peek()]) {
                result[stack.pop()] = arr[i];
            }
            stack.push(i);
        }
        return result;
    }
}

/*


[6,2,4]
we should remain bigger one until last

8

6, 4

24


x3 x2. x1 x4 (x5)

[1, 0, 3, 4]

if we want to remove 1,
if 1, 0 merge -> 1 still here, so we should choose bigger neighbor

[2, 1, 0, 3, 4]

1* min(2, 3)
     c
  a. c 
 xa bc 
xxa bc



our goal: 
keep remove small one, at last remain biggest

in this way, we can get min cost

if we choose removing bigger one, this bigger one still remain in next iteration, the cost will be higher

choose 2 number
a*b where b >= a

min cost is a*b
a already small one, so the key is b
b can be from a's left or right bigger neighbor (b >= a) (and first one, because it's more close)
and for better b, it's min(left_b, right_b)

so the ans is a* min(left_b, right_b)

how do we know left_b, right_b ? cal nextGreater and prevGreater


equal case need to include = (in one side, here I choose next Greater has =, but prevGreater doesn't have =)


*/
```ja