首页 > 试题广场 >

单调栈

[编程题]单调栈

热度指数：7377 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个长度为 $n$ 的可能含有重复值的数组 $nums$ ，找到每一个位置 $i$ 左边最近的位置 $l$ 和右边最近的位置 $r$ ， $nums_l$ 和 $nums_r$ 比 $nums_i$ 小。

请设计算法，返回一个二维数组，表示所有位置相应的信息。位置信息包括：两个数字 $l$ 和 $r$ 。如果不存在，则值为 -1，下标从 0 开始。

数据范围： $1 \le n \le 10^5$ ， $-10^9 \le nums_i \le 10^9$

进阶：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

示例1

输入

[3,4,1,5,6,2,7]

输出

[[-1,2],[0,2],[-1,-1],[2,5],[3,5],[2,-1],[5,-1]]

示例2

输入

[1,1,1,1]

输出

[[-1,-1],[-1,-1],[-1,-1],[-1,-1]]

算法知识视频讲解

Java

牛客148901号

import java.util.*;
public class Solution {
    public int[][] foundMonotoneStack (int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        int n = nums.length;
        int[][] result = new int[n][2];

        LinkedList<Integer> stack = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            result[i] = new int[2];
            while (!stack.isEmpty() && nums[i] <= nums[stack.peek()]) {
                stack.pop();
            }
            int left = stack.isEmpty() ? -1 : stack.peek();
            result[i][0] = left;
            stack.push(i);
        }
        stack.clear();

        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[i] <= nums[stack.peek()]) {
                stack.pop();
            }
            int right = stack.isEmpty() ? -1 : stack.peek();
            result[i][1] = right;
            stack.push(i);
        }

        return result;
    }
}

发表于 2024-05-19 16:05:27 回复(0)

Java

梁山教父

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int一维数组 
     * @return int二维数组
     */
    public int[][] foundMonotoneStack (int[] nums) {
        // write code here
        int arr[][]=new int[nums.length][2];
        for(int i=0;i<nums.length;i++){
            int left=-1;
            int right=-1;
            //最左边
            if(i==0){
                //左
                arr[i][0]=-1;
                //右遍遍历寻找最近比arr[i]小的值
                for(int j=i+1;j<arr.length;j++){
                    if(nums[j]<nums[i]){
                        right=j;
                        break;
                    }
                }
                arr[i][1]=right;
                
            }
            //最右边
            if(i==nums.length-1){
                //右
                arr[i][1]=-1;
                //左遍历寻找最近比arr[i]小的值
                for(int j=i-1;j>=0;j--){
                    if(nums[j]<nums[i]){
                        left=j;
                        break;
                    }
                }
                arr[i][0]=left;
            }
            //中间情况
            if(i!=0&&i!=nums.length-1){
                //左遍历寻找最近比arr[i]小的值
                for(int j=i-1;j>=0;j--){
                    if(nums[j]<nums[i]){
                        left=j;
                        break;
                    }
                }
                arr[i][0]=left;
                //右遍历寻找最近比arr[i]小的值
                for(int j=i+1;j<nums.length;j++){
                    if(nums[j]<nums[i]){
                        right=j;
                        break;
                    }
                }
                arr[i][1]=right;
            }
        }
        return arr;
    }
}

发表于 2023-05-24 18:10:57 回复(0)

Java

古月随风

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型二维数组
     */
    public int[][] foundMonotoneStack (int[] nums) {
        // write code here
        int[][] res = new int[nums.length][2];
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < nums.length; i++){
            while(!stack.isEmpty() && nums[stack.peek()] > nums[i]){
                int j = stack.pop();
                res[j][1] = i;
            }
            if(stack.isEmpty() || nums[stack.peek()] == nums[i]){
                res[i][0] = -1;
            }else{
                res[i][0] = stack.peek();
            }
            stack.push(i);
        }
        while(!stack.isEmpty()){
            res[stack.pop()][1] = -1;
        }
        return res;
    }
}

发表于 2022-09-13 19:24:51 回复(0)

Java

giasodgo

public class Solution {
    public int[][] foundMonotoneStack (int[] nums) {
    	//由于本体存在重复值，需要使用双向链表存放相同值
        Stack<LinkedList<Integer>> stack = new Stack<>();
        //存放结果的数组
        int result[][] = new int[nums.length][2];
        //依次遍历nums中每一个元素，i为数组的下标
        for(int i=0;i<nums.length;i++) {
        	//栈本身遵顼从小到大的单调原则，如果出现反例则陆续从栈中弹出元素直到符合原则
        	//弹出的元素即是需要处理的信息
        	while(!stack.isEmpty()&&nums[stack.peek().peekLast()]>nums[i]) {
        		//取出栈顶的链表，从尾部开始一次赋值
        		LinkedList<Integer> tmp = stack.pop();
        		while(!tmp.isEmpty()) {
        			int index = tmp.pollLast();
        			//如果弹出元素后栈为空则left值为-1.否则left的值为当前栈顶链表的尾元素的值
        			//right值为即将进入栈的元素，下标就是i
        			if(stack.isEmpty()) {
        				result[index][0]=-1;
        				result[index][1]=i;
        			}
        			else {
        				result[index][0]=stack.peek().peekLast();
            			result[index][1]=i;
        			}
        		}
        	}
        	//每遍历一个元素，相当于处理的是之前的元素，处理之后该元素仍需要入栈
        	//如果该元素的值和当前栈顶元素对应的值相等，则添加到一个链表中，否则创建一个新链表
        	if(!stack.isEmpty()&&nums[stack.peek().peekLast()]==nums[i]) {
        		stack.peek().addLast(i);
        	}
        	else {
        		LinkedList<Integer> res = new LinkedList<>();
        		res.addLast(i);
        		stack.add(res);
        	}
        }
        //此时所有的元素已经遍历完成，该添加进去的元素已经添加过了
        //此时栈里剩下的元素都是符合单调栈原则从小到大排列的
        //依次从栈顶弹出元素，right值为-1，left值为弹出后此时栈顶元素的链表尾部的下标
        //情况与上面类似，只不过right值为-1，当栈弹空时left为-1
        while(!stack.isEmpty()) {
        	LinkedList<Integer> tmp = stack.pop();
        	while(!tmp.isEmpty()) {
        		int index = tmp.pollLast();
        		if(stack.isEmpty()) {
        			result[index][0]=-1;
        			result[index][1]=-1;
        		}else {
        			result[index][0]=stack.peek().peekLast();
        			result[index][1]=-1;
        		}
        	}
        }
        return result;
    }
}

感觉写的挺清楚的，就是挺繁琐的，耗时有点高

发表于 2022-08-22 20:09:05 回复(1)

Java

ngcmz7

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int一维数组 
     * @return int二维数组
     */
    public int[][] foundMonotoneStack (int[] nums) {
        // write code here
        Stack<Integer> stack = new Stack<>();
        int[][] result = new int[nums.length][2];
        stack.push(-1);
        for(int i=0; i<nums.length; i++) {
            
            while(stack.peek()!=-1 && nums[stack.peek()]>nums[i]) {
                //因为比较的数字一定比栈顶元素小，所以这里可以设定每个栈顶元素的右边较小数
                result[stack.peek()][1] = i;
                stack.pop();
            }
            //上面while循环中条件必须是>，不能是>=，因为等于的情况不能把结果加入结果集，需要单独提出来讨论
            //（如果与栈顶元素相等说明自己左边的最近较小数与栈顶元素左边较小数一样，如果不相等说明栈顶元素就是左边的最近较小数）。
            if(stack.peek()!=-1 && nums[stack.peek()]==nums[i]) {
                result[i][0] = result[stack.peek()][0];
            }else {
                result[i][0] = stack.peek();
            }
            stack.push(i);
        }
        //stack中剩余的说明这些数字右边都没有比自己小的数字（因为是单调递增栈），那么把他们的结果集里第二个数字设为-1
        while(stack.peek()!=-1){
            result[stack.pop()][1] = -1;
        }
        return result;
    }
}

发表于 2022-04-04 17:56:42 回复(0)

Java

努力的阿小飞

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int一维数组 
     * @return int二维数组
     */
    public int[][] foundMonotoneStack (int[] nums) {
        Deque<Integer> stack = new LinkedList<>();
        stack.push(-1);
        int len = nums.length;
        int[][] res = new int[len][2];
        for(int i = 0; i < len; i++){
            while (stack.peek() != -1 && nums[stack.peek()] >= nums[i]){
                stack.poll();
            }
            res[i][0] = stack.peek();
            stack.push(i);
        }
        stack.clear();
        stack.push(-1);
        for(int i = len - 1; i >= 0; i--){
            while (stack.peek() != -1 && nums[stack.peek()] >= nums[i]){
                stack.poll();
            }
            res[i][1] = stack.peek();
            stack.push(i);
        }
        return res;
    }
}

发表于 2022-03-07 20:34:57 回复(0)

Java

FriskKiddo

    public int[][] foundMonotoneStack (int[] nums) {
        // write code here
        //维持两个单调栈，一个从nums头到尾构建单调栈，一个从nums尾到头构建单调栈
        Deque<Integer> stack = new LinkedList<>();
        Deque<Integer> reStack = new LinkedList<>();
        int[][] res = new int[nums.length][2];
        stack.push(-1);
        reStack.push(-1);
        for (int i = 0, j = nums.length - 1; i < nums.length; i++, j--) {
            int cur = nums[i], reCur = nums[j];
            while (stack.peek() != -1 && nums[stack.peek()] >= nums[i]) {
                stack.pop();
            }
            //添加左边
            res[i][0] = stack.peek();
            stack.push(i);
            
            while (reStack.peek() != -1 && nums[reStack.peek()] >= nums[j]) {
                reStack.pop();
            }
            //添加右边
            res[j][1] = reStack.peek();
            reStack.push(j);
        }
        
        return res;
    }

发表于 2022-02-22 16:51:14 回复(1)

Java

不爱吃烤肠

时间复杂度不可能O(n)啊

发表于 2021-12-16 15:21:28 回复(0)

Java

pein531

保持栈底往栈顶是单调递增的，在弹栈时生成信息

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int一维数组 
     * @return int二维数组
     */
    public int[][] foundMonotoneStack (int[] nums) {
        // write code here
        int[][] res = new int[nums.length][2];
        for(int i = 0; i < nums.length; i++){
            res[i][0] = -1;
            res[i][1] = -1;
        }
        Stack<LinkedList<Integer>> stack = new Stack<>();     // 栈底往栈顶保持单调递增
        for(int i = 0; i < nums.length; i++){
            if(stack.isEmpty()){
                LinkedList<Integer> list = new LinkedList<>();
                list.add(i);
                stack.push(list);
            }else{
                if(nums[i] == nums[stack.peek().peekLast()]){
                    stack.peek().add(i);
                    continue;
                }else if(nums[i] < nums[stack.peek().peekLast()]){
                    while(!stack.isEmpty() && nums[i] < nums[stack.peek().peekLast()]){
                        // 单调性被破坏，开始弹栈生成信息
                        Iterator<Integer> list = stack.pop().iterator();
                        while(list.hasNext()){
                            int curIdx = list.next();
                            res[curIdx][1] = i;       // 栈顶每个元素右边比它小的都是nums[i]
                            // 栈顶每个元素左边比它小是下面压着的数，下面没有压那就是-1
                            if(!stack.isEmpty())
                                res[curIdx][0] = stack.peek().peekLast();
                            else
                                res[curIdx][0] = -1;
                        }
                    }
                }
                LinkedList<Integer> list = new LinkedList<>();
                list.add(i);
                stack.push(list);
            }
        }
        // 清算阶段，将栈中所有元素左边比它小的第一个数找到
        while(!stack.isEmpty()){
            Iterator<Integer> iter = stack.pop().iterator();
            while(iter.hasNext()){
                if(!stack.isEmpty())
                    res[iter.next()][0] = stack.peek().peekLast();
                else
                    res[iter.next()][0] = -1;
            }
        }
        return res;
    }
}

发表于 2021-11-19 11:59:52 回复(0)

Java

惠灵顿靖

import java.util.*;
//七刷，弹压栈找离某数最近的左右节点
public class Solution {
   //
   public int[][] foundMonotoneStack (int[] nums) {
       // write code here
       int len = nums.length;
       // 返回的数组构造
       int[][] ans = new int[len][2];
       // 用栈保存
       Stack<Integer> stack = new Stack<>();
       // 从左往右，依次进行入栈，保存从左到右的升序的值
       for(int i = 0; i < len; i++){
           // 如果栈里面的值都比其大，就pop
           while(!stack.isEmpty() && nums[stack.peek()] >= nums[i]) stack.pop();
           // 栈空，说明nums[i]左边没有比他小的值
           if(stack.isEmpty()){
               ans[i][0] = -1;
           } else {
               // 如果有比他小的，那么栈中的第一个元素的值就是离他最近的
               ans[i][0] = stack.peek();
           }
           stack.push(i);
       }
       // 思路跟上面的一样，从右往左，保存升序值
       stack.clear();
       for(int i = len - 1; i >= 0; i--){
           while(!stack.isEmpty() && nums[stack.peek()] >= nums[i]) stack.pop();
           if(stack.isEmpty()){
               ans[i][1] = -1;
           } else {
               ans[i][1] = stack.peek();
           }
           stack.push(i);
       }
       return ans;
   }
}

发表于 2021-10-02 10:24:27 回复(0)

Java

Sout_Hello_World

public int[][] foundMonotoneStack (int[] nums) {
        // write code here
        int n = nums.length;
        int[][] ans = new int[n][2];
        for(int i=0;i<n;i++)
            Arrays.fill(ans[i],-1);
        Stack<int[]> s1 = new Stack();
        Stack<int[]> s2 = new Stack();
        for(int i=0;i<n;i++){
            while(!s1.isEmpty() && s1.peek()[1]>nums[i]){
                int x = s1.peek()[0],y = s1.peek()[1];
                ans[x][1] = i;
                s1.pop();
            }
            s1.push(new int[]{i,nums[i]});
            
            while(!s2.isEmpty() && s2.peek()[1]>=nums[i]){
                s2.pop();
            }
            if(s2.isEmpty()){
                ans[i][0] = -1;
            }
            else{
                ans[i][0] = s2.peek()[0];
            }
            s2.push(new int[]{i,nums[i]});
        }
        return ans;
    }

发表于 2021-09-09 15:41:26 回复(0)