题目描述

有一种排序算法定义如下，该排序算法每次只能把一个元素提到序列的开头，例如2，1，3，4，只需要一次操作把1提到序列其实位置就可以使得原序列从小到大有序。 现在给你一个乱序的1～n的排列，请你计算最少需要多少次操作才可以使得原序列从小到大有序。

输入描述

输入第一行包含一个正整数n，表示序列的长度（1 < = n < = 100000 1<=n<=1000001<=n<=100000） 接下来一行有n个正整数，表示序列中的n个元素，中间用空格隔开。（1 < = a i < = n 1<=a_i<=n1<=a i ​ <=n）

输出描述

输出仅包含一个证书，表示最少的操作次数。

样例输入

4
2 1 3 4

样例输出

1

思路

找到一个最大的逆序的元素，答案就是小于等于这个元素的个数，因为这些小于等于这个元素的数全都得提到前面去。

比如2，1，3，4，最大的逆序值是1；
比如2，1，3，5，4，最大的逆序值是4；
找这个元素的可以用栈来找，把第一个数压栈，后面遇到大于栈顶的元素直接压栈，遇到小于的拿出来和当前最大的逆序数比较，更新一下最大值。

package com.yyc.test;

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

public class Test {

    public static void main(String[] args) {
        //test(new int[]{2, 1, 3, 4});
        test(new int[]{2, 1, 3, 5, 4});
    }
    public static int test(int[] nums) {
        int len = nums.length;
        if (len <= 1) {
            return 0;
        }
        Deque<Integer> stack = new ArrayDeque<>();
        int max = 0;
        stack.push(nums[0]);
        for (int i = 1; i < len; i++) {
            if (!stack.isEmpty() && stack.peek() <= nums[i]) {
                stack.push(nums[i]);
            } else {
                max = Math.max(max, nums[i]);
            }
        }
        return max;
    }
}