当风声吹乱你构想...
【题目】
给定一个不含有重复值的数组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;
}
}
网友评论