您现在的位置是：首页 >其他 >数据结构与算法-单调栈1网站首页其他

先介绍一下单调栈是什么

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

给定一个可能含有重复值的数组arr，i位置的数一定存在如下两个信息

1）arr[i]的左侧离i最近并且小于(或者大于)arr[i]的数在哪？

2）arr[i]的右侧离i最近并且小于(或者大于)arr[i]的数在哪？

如果想得到arr中所有位置的两个信息，怎么能让得到信息的过程尽量快。

如果用暴力方法每个位置都去看看左边和右边第一个比它小的数是哪个，那时间复杂度就是O（N^2）了，而单调栈的的每个元素都只有一次入栈和出栈的过程，也就是说时间复杂度是O(2N)，省略常数时间O(N)

我们来解析一下[3,4,2,6,7,1,0,5]的入栈和出栈过程

本题单调栈原则：栈中元素从小到上越来越大

对于每一个数：如果栈顶元素小于他，直接入栈。如果栈顶元素大于它弹出栈顶，然后继续和下一个栈顶比较，弹出的时候计算弹出元素的左边第一个比它小的（它压着的那个）和右边第一个比它小的(把他弹出那个)。

问题1：为什么右边第一个比它小的是把它弹出的那个？我们假设C入栈的时候要弹出B，那么C肯定是小于B的且我们是根据数组的顺序入栈的，C在原来数组中一定在B的右边，那C和B之间有没有可能有其他小于B的元素呢？不可能的，如果有的话就把B弹出了，轮不到C来弹出B

问题2：为什么左边第一个比它小的是它压着的那个？假设B下面压着A，那数组中A肯定在B的左边，因为B压在A的上面，所以A一定比B小，否则B入栈的时候A就弹出了，那A和B之间有没有可能有其他小于B的元素呢？不可能的，如果有其他小于B的元素，理论上讲有两种可能(如果存在假设为X):1.X大于A小于B，那B下面压着的应该是X，而我们现在B下面压着A  2.X小于B且X小于A，那X入栈的时候A就应该弹出了，现在A没弹出，说明这种可能性不存在

 最后把数组中的元素单独弹出：

（1）右边比它小的不存在，这个好解释，如果右边有比它小的，那他就不会在栈里，而应该被弹出了。

（2）左边第一个比它小的就是它压着的，这个参考下上面的问题2

以上讨论的是无重复的情况，下面讨论一下有重复值的情况

如果有重复值的话，我们把结构变更为栈中每个元素都是链表

 左边比它小的是它压着那个链表的最后一个位置（只有一个就是那个位置）

好吧，接着上代码

package dataStructure.danDiaoZhan;

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

public class GetNearLess {
    public static int[][] getNearLessNoRepeat(int[] nums) {
        //没有元素我给你返回给鸟啊
        if(nums == null || nums.length == 0) {
            return null;
        }
        //返回值数组，lessArr[i][0]表示i位置的左边第一个比他小的数的下标，
        //lessArr[i][1]表示i位置的右边第一个比他小的数的下标，
        int[][] lessArr = new int[nums.length][2];
        //单调栈栈自底到顶依次增大的原则
        Stack<Integer> stack = new Stack<>();
        //从0到nums.length-1挨个入栈
        for(int i = 0; i < nums.length; i++) {
            //如果栈不为空并且栈顶元素大于当前元素，如果这个时候直接入栈就违反自底到顶依次增大的原则
            //先把大于当前数的都弹出再入栈
            while(!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
                int popNum = stack.pop();
                //它弹出后栈是不是为空，就是它原来在栈里有没有压着其他元素，有的话左边第一个比他小的就是这个元素
                lessArr[popNum][0] = stack.isEmpty()? -1 : stack.peek();
                //右边第一个比他小的是把它弹出那个，也就是当前的i
                lessArr[popNum][1] = i;
            }
            //不符合要求的都弹出了，栈为空或者栈里的都是比当前元素小的，直接入栈
            stack.push(i);
        }
        //如果最后所有元素都入栈过之后，栈不为空，需要单独进行结算
        while(!stack.isEmpty()) {
            int popNum = stack.pop();
            //它弹出后栈是不是为空，就是它原来在栈里有没有压着其他元素，有的话左边第一个比他小的就是这个元素
            lessArr[popNum][0] = stack.isEmpty()? -1 : stack.peek();
            //单独结算这些肯定不存在右边比他小的，因为如果右边有比他小的，单独结算之前就弹出了
            lessArr[popNum][1] = -1;
        }
        return lessArr;
    }

    public static int[][] getNearLess(int[] nums) {
        //没有元素我给你返回给鸟啊
        if(nums == null || nums.length == 0) {
            return null;
        }
        //返回值数组，lessArr[i][0]表示i位置的左边第一个比他小的数的下标，
        //lessArr[i][1]表示i位置的右边第一个比他小的数的下标，
        int[][] lessArr = new int[nums.length][2];
        //单调栈栈自底到顶依次增大的原则,这个方法栈里面的元素变成了ArrayList
        //这里为什么要使用ArrayList？因为我们后面会用到很多的list.getIndex(list.size()-1)这一类的操作
        //ArrayList效率高，而LinkedList需要从头开始找到尾
        Stack<ArrayList<Integer>> stack = new Stack<>();
        //从0到nums.length-1依次入栈
        for(int i = 0; i < nums.length; i++) {
            //第一步：把栈中大于它的弹出
            while(!stack.isEmpty() && nums[stack.peek().get(0)] > nums[i]) {
                ArrayList<Integer> popList = stack.pop();
                for(int popNum : popList) {
                    //如果当前list弹出后栈里还有元素，说明它原来在栈里是压着元素的，而它压着的第一个list的最后一个元素就是它左边第一个小于它的数
                    lessArr[popNum][0] = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
                    lessArr[popNum][1] = i;
                }
            }
            //第二步:把自己放入栈里
            //这里需要判断一下当前元素和栈顶元素是不是相等，当然首先要判断栈里有没有元素
            if(!stack.isEmpty() && nums[i] == nums[stack.peek().get(0)]) {
                ArrayList<Integer> peekList = stack.peek();
                peekList.add(i);
            } else {
                ArrayList<Integer> newList = new ArrayList<>();
                newList.add(i);
                stack.push(newList);
            }
        }
        //单独弹出和结算的过程
        while(!stack.isEmpty()) {
            ArrayList<Integer> popList = stack.pop();
            for(int popNum : popList) {
                //如果当前list弹出后栈里还有元素，说明它原来在栈里是压着元素的，而它压着的第一个list的最后一个元素就是它左边第一个小于它的数
                lessArr[popNum][0] = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
                //既然还在栈里，说明它的右边没有比它小的，不然那个数入栈的时候它就被弹出了
                lessArr[popNum][1] = -1;
            }
        }
        return lessArr;
    }
    public static void main(String[] args) {
        int[] nums = {3,4,2,6,7,1,0,5};
        int[][] lessArr = getNearLessNoRepeat(nums);
        printArr2D(lessArr);
        System.out.println("=============================");
        int[] numsRepeat = {1,3,4,5,4,3,1,2};
        int[][] lessArrRepeat = getNearLess(numsRepeat);
        printArr2D(lessArrRepeat);
    }

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

注意：代码里的getNearLess方法适用于有重复和无重复的情况，而getNearLessNoRepeat只能用于无重复值的情况。代码中我把图中的链表替换为了ArrayList，原因是我们用到了大量的list.get(list.size()-1)的操作，ArrayList是根据下标寻址的，效率更高，而LinkedList是从头到尾遍历。当然LinkedList是有getLast方法的，效率是一样的，哈哈，喜欢就好，我就喜欢ArrayList

每个有疑问的地方我都加了注释，应该不难理解，有疑问可以随时私信我，保证讲解清楚