每个元素为最大值的最大范围

/*
 * Leetcode 2832: 每个元素为最大值的最大范围
 * 
 * 题目思路：
 * 给定一个数组，要求找到每个元素在数组中作为最大值的最大范围。也就是说，
 * 对于数组中的每个元素，找到包含它且它是最大值的最长子数组范围。
 * 
 * 方法：
 * 1. 我们可以使用单调栈来解决这个问题。
 * 2. 先从左到右遍历数组，找到每个元素左侧第一个比它大的元素的位置。
 * 3. 再从右到左遍历数组，找到每个元素右侧第一个比它大的元素的位置。
 * 4. 通过左侧和右侧第一个比它大的元素的位置，可以确定该元素为最大值的最大范围。
 */
import java.util.*;
import java.util.stream.*;

public class MaxRangeForEachElementStream {
    public int[][] maxRange(int[] nums) {
        int n = nums.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();

        // 找到每个元素左侧第一个比它大的元素的位置
        IntStream.range(0, n).forEach(i -> {
            while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {
                stack.pop();
            }
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        });

        stack.clear(); // 清空栈用于下一次遍历

        // 找到每个元素右侧第一个比它大的元素的位置
        IntStream.iterate(n - 1, i -> i >= 0, i -> i - 1).forEach(i -> {
            while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {
                stack.pop();
            }
            right[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        });

        // 计算每个元素为最大值的最大范围
        return IntStream.range(0, n).mapToObj(i -> new int[]{left[i] + 1, right[i] - 1}).toArray(int[][]::new);
    }
}