所有子数组最小值中的最大值

/*
 * LeetCode Problem 1950: Maximum of Minimum Values in All Subarrays using Java Streams
 * 
 * Problem Statement:
 * Given an array of integers, find the maximum of the minimum values in all subarrays of the array.
 * 
 * Approach:
 * 1. Use a monotonic stack to find the previous and next less elements for each element in the array.
 * 2. Calculate the contribution of each element as the minimum in its subarrays.
 * 3. Aggregate the results to find the maximum of these minimum values.
 */

import java.util.Arrays;
import java.util.Stack;

public class Solution {
    public int maxOfMinValues(int[] arr) {
        int n = arr.length;
        int[] previousLess = new int[n];
        int[] nextLess = new int[n];
        Stack<Integer> stack = new Stack<>();

        // Find previous less for each element
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                stack.pop();
            }
            previousLess[i] = (stack.isEmpty()) ? -1 : stack.peek();
            stack.push(i);
        }

        stack.clear();

        // Find next less for each element
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                stack.pop();
            }
            nextLess[i] = (stack.isEmpty()) ? n : stack.peek();
            stack.push(i);
        }

        // Calculate maximum of minimum values in all subarrays
        int[] result = new int[n + 1];
        Arrays.fill(result, Integer.MIN_VALUE);
        for (int i = 0; i < n; i++) {
            int length = nextLess[i] - previousLess[i] - 1;
            result[length] = Math.max(result[length], arr[i]);
        }

        // Fill in the rest of the results array
        for (int i = n - 1; i >= 1; i--) {
            result[i] = Math.max(result[i], result[i + 1]);
        }

        return result[1]; // result[1] holds the final answer
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] arr = {1, 2, 3, 4, 5};
        System.out.println(sol.maxOfMinValues(arr)); // Expected output: 1
    }
}