题解 | #单调栈#

先计算每一个i位置右边离i位置最近且比位置arr[i]小的位置

使用单调递增栈找到右边离i位置最近且比位置arr[i]小的位置

先计算每一个i位置左边边离i位置最近且比位置arr[i]小的位置

最后合并right数组 与left数组

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int一维数组 
     * @return int二维数组
     */
    public int[][] foundMonotoneStack (int[] nums) {
        // write code here
        int len  = nums.length;
        if(nums == null || len == 0){
            return new int[len][2];
        }
        int[][] res = new int[len][2];
        int[] right = new int[len];
        Arrays.fill(right,-1);
        // 单调递增栈
        Deque<Integer> stack = new ArrayDeque<>();
        for(int i = 0;i<len;i++){
            int num = nums[i];
            while(!stack.isEmpty()&&(nums[stack.peekLast()]>num)){
                int curr = stack.peekLast();
                right[curr] = i;
                stack.pollLast();
            }
            stack.offerLast(i);
        }
        stack.clear();
        int[]  left = new int[len];
                Arrays.fill(left,-1);
        for(int i = len-1;i>=0;i--){
               int num = nums[i];
            while(!stack.isEmpty()&&(nums[stack.peekLast()]>num)){
                int curr = stack.peekLast();
                left[curr] = i;
                stack.pollLast();
            }
            stack.offerLast(i);
        }
        for(int i=0;i<len;i++){
            int[] temp = new int[]{left[i],right[i]};
            res[i] = temp;
        }
        return res;
    }
}