锐客网

  1. 首页 > it技术 > >

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

javaleetcode

数据结构与算法|单调栈-部分有序
文章图片

题目 【数据结构与算法|单调栈-部分有序】面试题 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 deque = new ArrayDeque<>(); int start = Integer.MAX_VALUE; // start的位置对应的可能被更新后的实际value值 int startToValue = https://www.it610.com/article/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}; } }

数据结构与算法|单调栈-部分有序
文章图片

    推荐阅读


    上一篇：笔记|JAVA中的练习

    下一篇：软件开发架构演变过程