单调栈结构

简介: 单调栈结构

单调栈是什么?

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

给定一个可能含有重复值的数组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");
    }
}
相关文章
|
23小时前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
19天前
初步认识栈和队列
初步认识栈和队列
47 10
|
14天前
数据结构(栈与列队)
数据结构(栈与列队)
15 1
|
18天前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
54 1
|
15天前
【数据结构】-- 栈和队列
【数据结构】-- 栈和队列
12 0
|
19天前
探索顺序结构:栈的实现方式
探索顺序结构:栈的实现方式
|
19天前
|
存储 C语言
栈和队列题目练习
栈和队列题目练习
13 0
|
27天前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
84 64
|
20天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
18 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
2月前
|
算法 安全 测试技术
golang 栈数据结构的实现和应用
本文详细介绍了“栈”这一数据结构的特点,并用Golang实现栈。栈是一种FILO(First In Last Out,即先进后出或后进先出)的数据结构。文章展示了如何用slice和链表来实现栈,并通过golang benchmark测试了二者的性能差异。此外,还提供了几个使用栈结构解决的实际算法问题示例,如有效的括号匹配等。
golang 栈数据结构的实现和应用