题解 |中等算法 #单调栈#

思路：当前数分别跟左边和右边比一遍，获取第一个小的值下标

1.循环比较赋值，就是时间复杂度有点高

• 时间复杂度 n^2
• 空间复杂度 1个二维数组 2个常量

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int一维数组 
     * @return int二维数组
     */
    public int[][] foundMonotoneStack (int[] nums) {
        // write code here
        int length = nums.length;
        int[][] ints= new int[length][2];
        for(int i=0;i<length;i++){
            int leftV=-1;
            int rightV=-1;
            for(int left=i-1;left>=0;left--){
                if(nums[i]>nums[left]){
                    leftV=left;
                    break;
                }
            }
            for(int right=i+1;right<length;right++){
                if(nums[i]>nums[right]){
                    rightV=right;
                    break;
                }
            }
            ints[i][0]=leftV;
            ints[i][1]=rightV;

        }
        return ints;
    }
}

2.利用栈存储下标，从左和从右遍历数组,以从左为例，空栈时，说明左边无数据，左边不存在最小数，即下标为-1，一个一个弹出下标，获取对应下标的数组值（当前值的下标比栈中的值要向前1个），小于当前值则返回栈内最新值，大于则弹出继续比较，直到空栈即找不到，存入-1.并存入当前下标，进行下一次比较

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int一维数组 
     * @return int二维数组
     */
    public int[][] foundMonotoneStack (int[] nums) {
        // write code here
        int length = nums.length;
        int[][] ints= new int[length][2];
        Stack<Integer> stack = new Stack();
        for(int i=0;i<length;i++){
            while(!stack.isEmpty()&& nums[stack.peek()]>=nums[i]){
                stack.pop();
            }
            if(stack.isEmpty()){
                ints[i][0]=-1;
            }else{
                ints[i][0]=stack.peek();
            }
            stack.push(i);
        }
        stack.clear();
        for(int i=length-1;i>=0;i--){
            while(!stack.isEmpty()&& nums[stack.peek()]>=nums[i]){
                stack.pop();
            }
            if(stack.isEmpty()){
                ints[i][1]=-1;
            }else{
                ints[i][1]=stack.peek();
            }
            stack.push(i);
        }
        return ints;
    }
}