[数据结构与算法]单调栈-部分有序

题目

面试题 16.16. 部分排序
给定一个整数数组，编写一个函数，找出索引m和n，只要将索引区间[m,n]的元素排好序，整个数组就是有序的。注意：n-m尽量最小，也就是说，找出符合条件的最短序列。函数返回值为[m,n]，若不存在这样的m和n（例如整个数组是有序的），请返回[-1,-1]。

示例：

输入： [1,2,4,7,10,11,7,12,6,7,16,18,19]
输出： [3,9]
提示：

0 <= len(array) <= 1000000

本题可以采用单调栈的思路，比如针对1,2,4,7,10,11,7,12,6,7,16,18,19 这个数组，

index = 6 的 7 首先不满足升序，因此需要调整把11和10 pop出去，然后放在index = 3的7后面，之所以可以pop出10和11的原因，是因为后续比较都可以index = 4的7来比，因为是找整个区间，所以除非后续的数组需要改动到index = 4的7之前，才会更新[m,n]的m。

这里面需要注意一个点那就是pop出去的数的最大值需要维护，这是为了计算出[m,n]的n，就是假设后续的数据都相对有序了，而且都比[m]对应的那个值大，但是如果比pop出去的数据小的话，那还是得排序的，就会继续更新n的取值。

代码如下：

package leetcode.editor.cn;

import java.util.ArrayDeque;
import java.util.Deque;

public class P1616 {


    public static void main(String[] args) {
        int[] arr = new int[]{1,2,4,7,10,11,7,12,6,7,16,18,19};

        P1616 p = new P1616();

        int[] ints = p.subSort(arr);

        System.out.println(ints[0] + " " + ints[1]);


        arr = new int[]{1,2,3,4,5,6,7,8};

        p = new P1616();

        ints = p.subSort(arr);

        System.out.println(ints[0] + " " + ints[1]);

    }


    public int[] subSort(int[] array) {

        Deque<Integer> deque = new ArrayDeque<>();
        int start = Integer.MAX_VALUE;
        // start的位置对应的可能被更新后的实际value值
        int startToValue = Integer.MAX_VALUE;
        int end = -1;
        int maxInRange = Integer.MIN_VALUE;

        for (int i = 0; i < array.length; i++) {
            boolean exeSwap = false;
            while (!deque.isEmpty() && array[i] < array[deque.peek()]) {
                exeSwap  = true;
                int popIndex = deque.pop();
                start = Math.min(start, popIndex);
                startToValue = array[i];
                maxInRange = Math.max(maxInRange, array[popIndex]);
            }

            deque.push(i);
            if (exeSwap || (start != Integer.MAX_VALUE && array[i] > startToValue && array[i] < maxInRange)) {
                end = i;
            }
        }

        return start != Integer.MAX_VALUE ? new int[]{start, end} : new int[]{-1,-1};


    }
}