原题（来源牛客网）
给定一个不含有重复值的数组 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}
}
解法
思想
单调栈，或使用动态规划的方式做，都可以达到线性时间复杂度。
代码
动态规划：（其实也是单调栈的思想）
class Solution {
public int[][] getNearLessNoRepeat(int[] arr) {
int[][] res = new int[arr.length][2];
//从左到右扫描
for (int i = 0; i < arr.length; i++) {
if(i == 0){
res[i][0] = -1;
continue;
}
int left = i-1;
while(left!=-1 && arr[left]>arr[i])
left = res[left][0];
if(left!=-1&&arr[left]<arr[i]) res[i][0] = left;
else res[i][0] = -1;
}
//从右到左扫描
for (int i = arr.length-1; i >= 0; i--) {
if(i == arr.length-1){
res[i][1] = -1;
continue;
}
int right = i+1;
while(right!=-1 && arr[right]>arr[i])
right = res[right][1];
if(right!=-1&&arr[right]<arr[i]) res[i][1] = right;
else res[i][1] = -1;
}
return res;
}
}
单调栈：
class Solution {
public int[][] getNearLessNoRepeat(int[] arr) {
int[][] res = new int[arr.length][2];
Stack<Integer> stack = new Stack<>();
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;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/%e6%95%b0%e7%bb%84%e5%85%83%e7%b4%a0%e5%b7%a6%e5%8f%b3%e4%b8%a4%e8%be%b9%e6%9c%80%e8%bf%91%e8%be%83%e5%b0%8f%e5%85%83%e7%b4%a0/
