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

原题(来源牛客网)

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

相关推荐

  • leetcode1160-拼写单词

    原题 给你一份『词汇表』(字符串数组) words 和一张『字母表』(字符串) chars。 假如你可以用 chars 中的『字母』(字符)拼写出 words 中的某个『单词』(字…

    算法 2020年3月17日
    0130
  • leetcode445-两数相加II

    原题 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。 你可以假设除了数字 0 之外,这两个数字都…

    算法 2020年4月14日
    0290
  • leetcode744-寻找比目标字母大的最小字母

    原题 给定一个只包含小写字母的有序数组letters 和一个目标字母 target,寻找有序数组里面比目标字母大的最小字母。 数组里字母的顺序是循环的。举个例子,如果目标字母tar…

    算法 2020年1月5日
    0220
  • 剑指offer44-数字序列中某一位的数字

    原题(来源Leetcode) 数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中,第5位(从下标0开始计数)是5,第13位是1,第19位…

    算法 2020年6月15日
    02900
  • leetcode135-分发糖果

    原题 老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。 你需要按照以下要求,帮助老师给这些孩子分发糖果: 每个孩子至少分配到 1 个…

    算法 2020年2月17日
    060
  • leetcode3-无重复字符的最长子串

    原题 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长…

    2019年12月26日
    0100
  • 剑指offer05-替换空格

    原题(来源Leetcode) 请实现一个函数,把字符串 s 中的每个空格替换成"%20"。 示例1: 输入: s = "We are happy." 输出: "We%20are%2…

    算法 2020年4月5日
    0110
  • leetcode560-和为K的子数组

    原题 给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。 示例 1: 输入: nums = [1,1,1], k = 2 输出: 2 , [1,1]…

    算法 2020年5月15日
    0470
  • leetcode236-二叉树的最近公共祖先

    原题 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 …

    2020年1月15日
    080
  • 剑指offer46-把数字翻译成字符串

    原题 给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编…

    算法 2020年2月29日
    0300

发表回复

登录后才能评论