原题（来源牛客网）

给定一个不含有重复值的数组 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/

数组元素左右两边最近较小元素

原题（来源牛客网）

解法

思想

代码

相关推荐

发表回复