单调栈结构

当风声吹乱你构想...
【题目】
给定一个不含有重复值的数组arr，找到每一个i位置左边和右边离i位置最近且值比arr[i]小的位置。返回所有未知的相应信息
举例：arr = {3,4,1,5,6,2,7}
返回如下二维数组作为结果： { {-1,2}， {0,2}， {-1，-1}， {2,5}， {3,5}， {2，-1}， {5，-1} }，其中，-1表示不存在

【要求】
时间复杂度为O(n)

【解答】
见源码

package pers.mao.stackAndQueue.demo_08;

import java.util.Stack;

/**
 * @author Mao Qingbo
 * @date 2020-10-27
 * 单调栈
 */
public class NearLessNoRepeat {
    public int [][] getNearLessNoRepeat(int [] arr){
        Stack<Integer> stack = new Stack<Integer>();
        int [][] res = new int[arr.length][2];
        for(int i = 0; i < arr.length; i ++){
            while(!stack.isEmpty() && arr[stack.peek()] > arr[i]){
                int popIndex = stack.pop();
                int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
                res[popIndex][0] = leftLessIndex;
                res[popIndex][1] = i;
            }
            stack.push(i);
        }
        while(!stack.isEmpty()){
            int popIndex = stack.pop();
            int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
            res[popIndex][0] = leftLessIndex;
            res[popIndex][1] = -1;
        }
        return res;
    }
}