题解 | #单调栈#

import java.util.*;


public class Solution {
    
//     public class ListNode {
//         public int val;
//         public ListNode next;
//         public ListNode(int val) {
//             this.val = val;
//         }
//     }
    
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int一维数组 
     * @return int二维数组
     */
    public int[][] foundMonotoneStack (int[] nums) {
        // write code here
        int[][] res = new int[nums.length][2]; // 定义一个二维数组，用于存放最终的返回结果
        Stack<ArrayList<Integer>> stack = new Stack<>(); // 定义一个栈
        for (int i = 0; i < nums.length; i++) {
            int index = i; // 当前所在的位置(下标)
            int val = nums[i]; // 当前所在位置存放的值
            while (!stack.isEmpty() && nums[stack.peek().get(0)] > val) {
                ArrayList<Integer> arrs = stack.pop(); // 栈中弹出一个链表
                for (int arr : arrs) {
                    res[arr][0] = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
                    res[arr][1] = index;
                }
            }
            if (stack.isEmpty()) { // 如果栈是空的，直接入栈即可
                ArrayList<Integer> arrs = new ArrayList<>(); // 创建一个链表
                arrs.add(index); // 将当前下标添加到链表中去
                stack.push(arrs);
            }
            else { // 如果栈不为空
                if (nums[stack.peek().get(0)] == val) {
                    ArrayList<Integer> arrs = stack.peek();
                    arrs.add(index);
                }
                else if (nums[stack.peek().get(0)] < val) {
                    ArrayList<Integer> arrs = new ArrayList<>();
                    arrs.add(index);
                    stack.push(arrs);
                }
            }
        }
        while (!stack.isEmpty()) {
            ArrayList<Integer> arrs = stack.pop();
            for (int arr : arrs) {
                res[arr][0] = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
                res[arr][1] = -1;
            }
        }
        return res;
    }
}