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

原题(来源牛客网)

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

(0)
彭晨涛彭晨涛管理者
上一篇 2020年4月26日
下一篇 2020年4月27日

相关推荐

  • leetcode238-除自身以外数组的乘积

    原题 给你一个长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积…

    算法 2020年6月4日
    080
  • leetcode95-不同的二叉搜索树II

    原题 给定一个整数 n,求以 1 ... n 为节点组成的二叉搜索树有多少种? 示例: 输入: 3 输出: [   [1,null,3,2],  &n…

    算法 2020年1月22日
    0700
  • leetcode1300-转变数组后最接近目标值的数组和

    原题 给你一个整数数组 arr 和一个目标值 target ,请你返回一个整数 value ,使得将数组中所有大于 value 的值变成 value 后,数组的和最接近 targe…

    算法 2020年6月14日
    0950
  • leetcode153-寻找旋转排序数组中的最小值

    原题 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值,…

    算法 2020年1月3日
    080
  • 蓝桥杯试题-小数第n位

    原题 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述   我们知道,整数做除法时,有时得到有限小数,有时得到无限循环小数。  如果我们把有限小数的末尾加上无限多个…

    算法 2020年2月29日
    080
  • leetcode54-螺旋矩阵

    原题 给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。 示例 1: 输入: [ [ 1, 2, 3 ], [ 4, 5, 6…

    算法 2019年11月15日
    080
  • 剑指offer04-二维数组中的查找

    原题(来源Leetcode) 在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个…

    算法 2020年4月4日
    0130
  • leetcode70-爬楼梯

    原题 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意: 给定 n 是一个正整数。  示例 1: 输入:…

    算法 2020年1月21日
    0840
  • leetcode283-移动零

    原题 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说…

    算法 2019年11月23日
    0100
  • leetcode704-二分查找

    原题 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。 示…

    算法 2019年12月29日
    070

发表回复

登录后才能评论