算法-16单调栈结构

2022/4/15 22:12:52

本文主要是介绍算法-16单调栈结构,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

单调栈(monotone-stack)是指栈内元素(栈底到栈顶)都是(严格)单调递增或者单调递减的。

如果有新的元素入栈,栈调整过程中 会将所有破坏单调性的栈顶元素出栈,并且出栈的元素不会再次入栈 。由于每个元素只有一次入栈和出栈的操作,所以 单调栈的维护时间复杂度是O(n) 。

单调栈性质:

  • 单调栈里的元素具有单调性。
  • 递增(减)栈中可以找到元素左右两侧比自身小(大)的第一个元素。

我们主要使用第二条性质,该性质主要体现在栈调整过程中,下面以自栈底到栈顶递增为例(假设所有元素都是唯一),当新元素入栈。

  • 对于出栈元素来说:找到右侧第一个比自身小的元素。
  • 对于新元素来说:等待所有破坏递增顺序的元素出栈后,找到左侧第一个比自身小的元素。

 

问题描述:给定不含重复值的数组arr,找到每个i位置左边和右边距离i最近的且值比i小的位置(没有返回-1),返回所有的位置信息。

输入描述:

第一行输入一个数字 n,表示数组 arr 的长度。

以下一行输出 n个数字,表示数组的值。

输出描述:

输出n行,每行两个数字 L 和 R,如果不存在,则值为-1,下标从0开始。

示例1

输入:
7
3 4 1 5 6 2 7

输出:
-1 2
0 2
-1 -1
2 5
3 5
2 -1
5 -1

思路

常规实现:时间复杂度O(n^2)实现简单,每个位置向左和向右遍历一遍。

import java.util.Scanner;
import java.util.Stack;

public class Main{
    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 void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            int[] data = new int[n];
            for(int i=0;i<data.length;i++) {
                data[i] = sc.nextInt();
            }
            //int[][] result = getNearLessNoRepeat(data);
            int[][] result = rightWay(data);
            StringBuilder sb = new StringBuilder();
            for(int i=0;i<result.length;i++) {
                sb.append(result[i][0]).append(" ").append(result[i][1]).append('\n');
            }
            System.out.print(sb);
        }
    }
}

 

单调栈实现:寻找两边距离arr[i]最近且arr[i]小的索引,保持栈顶到栈底单调递减(寻找比arr[i]大的值,单调递增),栈中存放索引值。

import java.util.Scanner;
import java.util.Stack;

public class Main{
    public static int[][] getNearLessNoRepeat(int[] arr) {
        int[][] res = new int[arr.length][2];
        Stack<Integer> stack = new Stack<Integer>();
        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;
                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 void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            int[] data = new int[n];
            for(int i=0;i<data.length;i++) {
                data[i] = sc.nextInt();
            }
            int[][] result = getNearLessNoRepeat(data);
            StringBuilder sb = new StringBuilder();
            for(int i=0;i<result.length;i++) {
                sb.append(result[i][0]).append(" ").append(result[i][1]).append('\n');
            }
            System.out.print(sb);
        }
    }
}

 

单调栈实现进阶问题:区别在于重复索引值用集合进行连接,栈中存放的是一个ArrayList。注意两点:

  • arr[i]左边应该是上一个位置最晚加入的那个(如果有多个元素)
  • 相等的情况直接在尾部加入,获取值的时候循环的获取该集合中的所有值(集合中元素值相等,索引值不同)
import java.util.List;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;


public class Main{
    public static int[][] getNearLess(int[] arr) {
        int[][] res = new int[arr.length][2];
        Stack <List<Integer>> stack = new Stack <List<Integer>>();
        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<Integer> list = new ArrayList<Integer>();
                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 void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] data = new int[n];
        for(int i=0;i<data.length;i++) {
            data[i] = sc.nextInt();
        }
        int[][] result = getNearLess(data);
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<result.length;i++) {
            sb.append(result[i][0]).append(" ").append(result[i][1]).append('\n');
        }
        System.out.print(sb);
    }
}

 

参考:https://www.jianshu.com/p/3c33d7087dfb



这篇关于算法-16单调栈结构的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程