单调栈结构

简介: 单调栈结构

单调栈是什么?

一种特别设计的栈结构,为了解决如下的问题:

给定一个可能含有重复值的数组arr,i位置的数一定存在如下两个信息
1) arr[i] 的左侧离 i 最近并且小于(或者大于)arr[i]的数在哪?
2) arr[i] 的右侧离 i 最近并且小于(或者大于)arr[i]的数在哪?
如果想得到arr中所有位置的两个信息,怎么能让得到信息的过程尽量快。
那么到底怎么设计呢?

要求时间复杂度为O(N)

package com.harrison.class14;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author Harrison
 * @create 2022-03-26-19:03
 * @motto 众里寻他千百度,蓦然回首,那人却在灯火阑珊处。
 */
public class Code01_MonotonousStack {
    /*
    arr=[   3,  1,  2,  3]
    index   0   1   2   3
    返回(记位置,没有就记-1):
        [
            0:[-1,  1]
            1:[-1, -1]
            2:[1,  -1]
            3:[2,  -1]
         ]
     */
    public static int[][] getNearLessNoRepeat(int[] arr){
        int[][] res=new int[arr.length][2];
        // 单调栈里只存下标
        Stack<Integer> stack=new Stack<>();
        // 遍历数组arr里的每一个数
        for(int i=0; i<arr.length; i++){
            while(!stack.isEmpty() && arr[stack.peek()]>arr[i]){
                int j=stack.pop();
                int leftLessIndex=stack.isEmpty()?-1:stack.peek();
                res[j][0]=leftLessIndex;
                res[j][1]=i;
            }
            stack.push(i);
        }
        while(!stack.isEmpty()){
            int j=stack.pop();
            int leftLessIndex=stack.isEmpty()?-1:stack.peek();
            res[j][0]=leftLessIndex;
            res[j][1]=-1;
        }
        return res;
    }

    public static int[][] getNearLess(int[] arr){
        int[][] res=new int[arr.length][2];
        Stack<List<Integer>> stack=new Stack<>();
        for(int i=0; i<arr.length; i++){
            while(!stack.isEmpty() && arr[stack.peek().get(0)]>arr[i]){
                List<Integer> popIs=stack.pop();
                int leftLessIndex=stack.isEmpty()?-1:stack.peek().get(stack.peek().size()-1);
                for(Integer popi:popIs){
                    res[popi][0]=leftLessIndex;
                    res[popi][1]=i;
                }
            }
            if(!stack.isEmpty() && arr[stack.peek().get(0)]==arr[i]){
                stack.peek().add(Integer.valueOf(i));
            }else{
                /*
                为什么用ArrayList而不用LinkedList?
                ArrayList拿最后一个位置的值比LinkedList快
                LinkedList需要全部遍历一遍(但是LinkedList有getLast()方法)
                 */
                ArrayList<Integer> list=new ArrayList<>();
                list.add(i);
                stack.push(list);
            }
        }
        while(!stack.isEmpty()){
            List<Integer> popIs=stack.pop();
            int leftLessIndex=stack.isEmpty()?-1:stack.peek().get(stack.peek().size()-1);
            for(Integer popi:popIs){
                res[popi][0]=leftLessIndex;
                res[popi][1]=-1;
            }
        }
        return res;
    }

    public static int[] getRandomArrayNoRepeat(int size){
        int[] arr=new int[(int)(Math.random()*size)+1];
        for(int i=0; i<arr.length; i++){
            arr[i]=i;
        }
        for(int i=0; i<arr.length; i++){
            int swapIndex=(int)(Math.random()*arr.length);
            int tmp=arr[swapIndex];
            arr[swapIndex]=arr[i];
            arr[i]=tmp;
        }
        return arr;
    }

    public static int[] getRandomArray(int size,int max){
        int[] arr=new int[(int)(Math.random()*size)+1];
        for(int i=0; i<arr.length; i++){
            arr[i]=(int)(Math.random()*max)-(int)(Math.random()*max);
        }
        return arr;
    }

    // 暴力解
    public static int[][] rightWay(int[] arr){
        int[][] res=new int[arr.length][2];
        for(int i=0; i<arr.length; i++){
            int leftLessIndex=-1;
            int rightLessIndex=-1;
            int cur=i-1;
            while(cur>=0){
                if(arr[cur]<arr[i]){
                    leftLessIndex=cur;
                    break;
                }
                cur--;
            }
            cur=i+1;
            while(cur<arr.length){
                if(arr[cur]<arr[i]){
                    rightLessIndex=cur;
                    break;
                }
                cur++;
            }
            res[i][0]=leftLessIndex;
            res[i][1]=rightLessIndex;
        }
        return res;
    }

    public static boolean isEqual(int[][] res1,int[][] res2){
        if(res1.length!=res2.length){
            return false;
        }
        for(int i=0; i<res1.length; i++){
            if(res1[i][0]!=res2[i][0] || res2[i][1]!=res2[i][1]){
                return false;
            }
        }
        return true;
    }

    public static void printArray(int[] arr){
        for(int i=0; i<arr.length; i++){
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int size=10;
        int max=20;
        int testTimes=200000;
        System.out.println("test begin");
        for(int i=0; i<testTimes; i++){
            int[] arr1=getRandomArrayNoRepeat(size);
            int[] arr2=getRandomArray(size,max);
            if(!isEqual(getNearLessNoRepeat(arr1),rightWay(arr1))){
                System.out.println("oops");
                printArray(arr1);
                break;
            }
            if(!isEqual(getNearLess(arr2),rightWay(arr2))){
                System.out.println("oops");
                printArray(arr2);
                break;
            }
        }
        System.out.println("test finish");
    }
}
相关文章
|
16天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
91 9
|
7天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
16 1
|
10天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
16天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
58 16
|
13天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
15天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
43 4
|
19天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
数据结构(栈与列队)
数据结构(栈与列队)
17 1
|
1月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
30 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
1月前
初步认识栈和队列
初步认识栈和队列
59 10