美文网首页
单调栈结构

单调栈结构

作者: Tank_Mao | 来源:发表于2020-10-29 22:26 被阅读0次

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

相关文章

  • 单调栈和应用实践

    什么是单调栈 单调栈的定义:单调栈即满足单调性的栈结构。与单调队列相比,其只在一端进行进出。 如何使用单调栈 单调...

  • 单调栈 2020-06-12(未经允许,禁止转载)

    1.单调栈 指栈内元素保持单调性的栈结构,分为单调增栈(栈底到栈顶元素递增)和单调减栈(栈底到栈顶元素递减) 2....

  • 单调栈结构

    当风声吹乱你构想...【题目】给定一个不含有重复值的数组arr,找到每一个i位置左边和右边离i位置最近且值比arr...

  • 题解——单调栈

    单调栈题解 单调栈结构 牛客链接 方法:单调栈 算法 这里维护一个单调递增栈,可以找到比当前元素要小的元约定:当前...

  • 数据结构--单调栈

    单调栈即满足单调性的栈结构。单调栈实际上就是栈,只是利用了一些巧妙的逻辑,使得每次新元素入栈后,栈内的元素都保持有...

  • Algorithm小白入门 -- 队列和栈

    队列和栈队列实现栈、栈实现队列单调栈单调队列运用栈去重 1. 队列实现栈、栈实现队列 队列是一种先进先出的数据结构...

  • 算法进阶二

    BFPRT算法: 介绍窗口以及窗口内最大值或最小值的更新结构(单调双向队列) 介绍单调栈结构

  • 1.单调栈

    一、单调栈定义 单调栈(monotone-stack)是指栈内元素(栈底到栈顶)都是(严格)单调递增或者单调递减的...

  • LeetCode刷题指北----单调栈

    1.什么是单调栈?有什么好处? 定义: 单调栈就是栈内元素递增或者单调递减的栈,并且只能在栈顶操作。单调栈的维护是...

  • C语言之单调栈

    单调栈 What 单调栈也是栈的一种,满足先进后出的原则,另外,单调栈中的元素是有序的,分为两种 单调递增栈:单调...

网友评论

      本文标题:单调栈结构

      本文链接:https://www.haomeiwen.com/subject/caolvktx.html