【算法】单调栈问题

冷不防 2024-03-16 09:55 71阅读 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表示不存在，比如arr中，0位置的左边没有元素，所以是-1.右边最小的是1这个数据位置，也就是index=2，所以得到\{-1，2\}。

如果我给定是一个可能含有重复值的数组arr呢？

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

## 思路分析 ##

如果是时间复杂度为O(N2)的，那么我们直接暴力解决即可，都是如果这样子做，这道题肯定就g了。

我们先来分析无重复的数组的情况。

原问题：  
准备一个栈，记为 Stack<Integer>，栈中放的元素是数组的位置，开始时stack 为空。如果找到每一个i位置左边和右边离i位置最近且值比 arrli\]小的位置，那么需要让stack 从栈顶到栈底的位置所代表的值是严格递减的；如果找到每一个i位置左边和右边离i位置最近且值比 arr\[i\]大的位置，那么需要让 stack 从栈顶到栈底的位置所代表的值是严格递增的。  
本题需要解决的是前者，但是对于后者,原理完全是一样的。

下面用例子来展示单调栈的使用和求解流程，初始时 arr = \{3,4,1,5,6,2,7\}，stack 从栈顶到栈底为：\{\}

遍历到arr\[0\]==3，发现stack为空，就直接放入0位置。stack 从栈顶到栈底为:\{0位置(值是3))；

遍历到arr\[1\]==4，发现直接放入1位置,不会破坏stack 从栈顶到栈底的位置所代表的值是严格递减的，那么直接放入。stack从栈顶到栈底依次为:(1位置(值是4)、0位置(值是3)；

遍历到arr\[2\]==1，发现直接放入2位置（值是1)，会破坏stack 从栈顶到栈底的位置所代表的值是严格递减的，所以从 stack开始弹出位置。如果x位置被弹出，在栈中位于x位置下面的位置，就是x位置左边离x位置最近且值比 arr\[x\]小的位置；  
当前遍历到的位置就是x位置右边离x位置最近且值比 arr\[x\]小的位置。  
从 stack弹出位置1,在栈中位于1位置下面的是位置0,当前遍历到的是位置2，所以 ans\[1\]=(0.2\}。  
弹出1位置之后，发现放入2位置（值是1)还会破坏stack 从栈顶到栈底的位置所代表的值是严格递减的，所以继续弹出位置0。  
在栈中位于位置0下面已经没有位置了，说明在位置О左边不存在比 arr\[0\]小的值，当前遍历到的是位置2，所以ans\[0\]=(-1,2\}。stack 已经为空，所以放入2位置（值是1)，stack从栈顶到栈底为:\{2位置(值是1));

遍历到 arr\[3\]==5，发现直接放入3位置，不会破坏stack 从栈顶到栈底的位置所代表的值是严格递减的，那么直接放入。stack 从栈顶到栈底依次为:3位置(值是5)、2位置(值是1);

遍历到 arr\[4\]==6，发现直接放入4位置，不会破坏 stack 从栈顶到栈底的位置所代表的值是严格递减的，那么直接放入。stack从  
栈顶到栈底依次为:\{(4位置(值是6)、3位置(值是5)、2位置(值是1);

遍历到 arr\[5\]==2，发现直接放入5位置，会破坏stack从栈顶到栈底的位置所代表的值是严格递减的，所以开始弹出位置。弹出位置4,栈中它的下面是位置3,当前是位置5, ans\[4\]=(3,5\}。弹出位置3，栈中它的下面是位置2，当前是位置5，ans\[3\]=(2,5\}。然后放入5位置就不会破坏stack的单调性了。stack从栈顶到栈底依次为:\{5位置(值是2)、2位置(值是1)\};

遍历到arr\[6\]==7，发现直接放入6位置，不会破坏stack从栈顶到栈底的位置所代表的值是严格递减的，那么直接放入。stack从栈顶到栈底依次为:\{6位置(值是7)、5位置(值是2)、2位置(值是1)\}。

遍历阶段结束后,清算栈中剩下的位置。

弹出6位置，栈中它的下面是位置5，6位置是清算阶段弹出的，所以 ans\[6\]=\{5,-1\];弹出5位置，栈中它的下面是位置2，5位置是清算阶段弹出的，所以 ans\[5\]=\{2,-1\];弹出2位置，栈中它的下面没有位置了，2位置是清算阶段弹出的，所以 ans\[2\]=(-1,-1\]。

至此，已经全部生成了每个位置的信息。

我们可以按照上面的流程写出如下的代码

public static int[][] monotonicStackNorepeat(int[] arr) {
        
            Stack<Integer> stack = new Stack<>();
            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;
                    //比栈顶元素右边小的元素的位置为i
                    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;
        }

对于进阶问题，她的情况是，可能出现重复的数据，但是大体的解答流程差不多，思路如下：

进阶问题，可能含有重复值的数组如何使用单调栈。其实整个过程和原问题的解法差不多。举个例子来说明，初始时 arr=\{3,1,3,4,3,5,3,2,2\]，stack从栈顶到栈底为：\{\}；

遍历到 arr\[0\]==3，发现stack为空，就直接放入0位置。stack 从栈顶到栈底为:\{0位置(值是3）\}；

遍历到arr\[1\]==1，从栈中弹出位置0,并且得到ans\[0\]=\[-1,1\}。位置1进栈，stack从栈顶到栈底为:\{1位置(值是1)\};

遍历到arr\[2\]==3，发现位置2可以直接放入。stack从栈顶到栈底依次为:\{2位置(值是3).1位置(值是1)\};

遍历到 arr\[3\]==4，发现位置3可以直接放入。stack从栈顶到栈底依次为:\{3位置(值是4)、2位置(值是3)、1位置(值是1)\};

遍历到arr\[4\]==3，从栈中弹出位置3，并且得到ans\[3\]=\{2,4\}。此时发现栈顶是位置2，值是3，当前遍历到位置4，值也是3，所以两个位置压在一起。stack 从栈顶到栈底依次为:\{ 2位置,4位置、1位置(值是1)\};

遍历到arr\[5\]==5，发现位置5可以直接放入。stack 从栈顶到栈底依次为:\{5位置(值是5)、2位置,4位置、1位置(值是1));

遍历到arr\[6\]==3，从栈中弹出位置5，在栈中位置5的下面是\[2位置,4位置\]，选最晚加入的4位置，当前遍历到位置6，所以得到 ans\[5\]=\{4,6\}。位置6进栈，发现又是和栈顶位置代表的值相等的情况，所以继续压在一起，stack 从栈顶到栈底依次为:\{ 2位置,4位置,6位置、1位置(值是1)\};

遍历到arr\[7\]==2，从栈中弹出\[2位置,4位置,6位置\],在栈中这些位置下面的是1位置，当前是7位置，所以得到ans\[2\]=(1,7\]、ans\[4\]=(1,7\]、ans\[6\]=\{1,7\}\]。位置7进栈，stack 从栈顶到栈底依次为:\{7位置(值是2)、1位置(值是1)\};

遍历到arr\[8\]==2，发现位置8可以直接进栈，并且又是相等的情况，stack从栈顶到栈底依次为:\{ 7位置,8位置、1位置(值是1)\}。

遍历完成后，开始清算阶段:

弹出\[7位置,8位置\],生成ans\[7\]=\{1,-1\]、ans\[8\]=\{1,-1\};弹出1位置，生成ans\[1\]=\{-1,-1\}。

完整代码贴在下面：

## 代码实现 ##

package com.base.learn.stack;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    import java.util.Stack;
    
    /**
     * @author: 张锦标
     * @date: 2023/5/28 11:00
     * MonotonicStack类
     * 单调栈题目
     */
    public class MonotonicStack {
        
        public static int[][] violentSolution(int[] arr) {
        
            int[][] res = new int[arr.length][2];
            for (int i = 0; i < arr.length; i++) {
        
                int leftMin = -1;
                int rightMin = -1;
                int cur = i - 1;
                while (cur >= 0) {
        
                    if (arr[cur] < arr[i]) {
        
                        leftMin = cur;
                        break;
                    }
                    cur--;
                }
                cur = i + 1;
                while (cur < arr.length) {
        
                    if (arr[cur] < arr[i]) {
        
                        rightMin = cur;
                        break;
                    }
                    cur++;
                }
                res[i][0] = leftMin;
                res[i][1] = rightMin;
            }
            return res;
        }
    
        public static int[][] monotonicStackNorepeat(int[] arr) {
        
            Stack<Integer> stack = new Stack<>();
            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;
                    //比栈顶元素右边小的元素的位置为i
                    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;
        }
    
        public static int[][] monotonicStackRepeat(int[] arr) {
        
            Stack<List<Integer>> stack = new Stack<>();
            int[][] res = new int[arr.length][2];
            for (int i = 0; i < arr.length; i++) {
        
                //如果当前栈不为空并且当前值比栈顶对应的元素小
                //那么就开始出栈 因为这说明栈内元素遇到了比自己小的数据了
                //并且一直出栈直到栈顶元素比当前元素小
                while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]) {
        
                    //出栈得到栈顶元素对应的索引
                    List<Integer> popList = stack.pop();
                    //判断栈顶元素的左边是否还有元素 如果有 那么比栈顶元素的左边最小就是这个元素
                    int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(
                            stack.peek().size()-1
                    );
                    for (Integer popi : popList) {
        
                        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{
        
                    //栈为空 或者当前元素与栈顶元素不一样 那么直接创建一个新的list
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(i);
                    stack.push(list);
                }
            }
            //清算阶段 对于还在栈中的元素
            while (!stack.isEmpty()) {
        
                //出栈得到栈顶元素对应的索引
                List<Integer> popList = stack.pop();
                //判断栈顶元素的左边是否还有元素 如果有 那么比栈顶元素的左边最小就是这个元素
                int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(
                        stack.peek().size()-1
                );
                for (Integer popi : popList) {
        
                    res[popi][0]=leftLessIndex;
                    res[popi][1] = -1;
                }
            }
            return res;
        }
    
        public static void main(String[] args) {
        
            System.out.println(Arrays.deepToString(monotonicStackNorepeat(new int[]{
        3,4,1,5,6,2,7})));
        }
    }