算法-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