Leetcode high frequency question: the array can be changed into a non descending state after at least several operations

LeetCode High frequency questions ： At least several operations can make the array non descending

Tips ： This topic is a series LeetCode Of 150 High frequency questions , The written examination and interview questions you will encounter in the future , They are basically adapted from this topic
Internet giants have raised a large number of people in the company ACM The big guys of the competition , After dinner, I will design test questions , Then go to test the candidates , All you have to do is learn the basic tree structure and algorithm , And then get through Ren Du's two veins , In response to the treacherous interview questions of the big factory written examination ！
If you don't learn data structures and algorithms well , Do a good job tearing up the code , Exercise problem-solving ability , You may be in the written interview process , I can't even understand the topic ！ For example, Huawei , Bytes or something , Enough to make you unable to read the question

Basic knowledge of ：
【1】LeetCode High frequency questions 300. The longest increasing subsequence

---

subject

author ： Cattle guest 40502855 Number
source ： Cattle from

Given a size of N An unordered array of arr, The following operations can be performed on each element in the array ：
Move elements to the head of the array
Move the element to the end of the array
Be careful ： The movement here is not done through the exchange of elements , Instead, move the element directly to the specified position , The empty position is filled by other elements in sequence .
ask ： At least through Several operations You can make the array non descending .

---

One 、 Examine the subject

Input ：
Enter a positive number in the first line n Representative array arr Number of elements of
The second line , give n A positive integer ai, Represents the elements in an array
1<=n<=3*10 Of 5 Power
1<=ai<=10 Of 9 Power

Output ：
a number ans, Represents the minimum number of times required to operate the array into a non descending state

such as
arr=19 7 8 25
First 8 Move to header
arr=8 19 7 25
And then 7 Move to header
7 8 19 25

2 It's done once

---

Learn about the longest increasing subsequence

19 7 8 25
The longest non decreasing subsequence length is 3
N Total length =4
N-3=1
Actually, you need to move 2 Time , How to explain ？

Or try a whole range ？？？
set up f(i) Yes, it will i After adjusting the position element , The minimum number of operations required

Main function call f(0 Position start ), until i To N Position out of bounds , Look at the minimum number of adjustments ？

Then let's discuss a wave , This f How to write

（0） When i=N When crossing the border , No need to transfer , operation 0 Time , return 0 Next time
（1） Anywhere i when ： It can make i The position does not move , Calculation operation 0 Time , have a look f（i+1）
（2） Anywhere i when ： It can make i Go to the head , Calculation operation 1 Time , The rest arr, have a look f（i+1）
（3） Anywhere i when ： It can make i Position to the tail , Calculation operation 1 Time , The rest arr, have a look f（i+1）
The answer to these three , Select the minimum value to return

Moved in the middle arr, We need to take it with us ？？？
This can , But this is a very bad way to try , because arr Always changing , And it's not a simple variable type , This method , stupid ！

Think of new ways

It is said to sort first ：

Need a size of n The array records the ordered results ,
Then compare one by one , The statistical sorting array corresponds to the Suffix Array , Its longest increasing subsequence ,
Last use n Subtract the length of this sequence

Like the one above 19 7 8 25
7 8 19 25 The index subscript array of this sort array corresponding to the original array is
1 2 0 3, find 1203 The longest continuity Just increment the subarray
—— Discontinuous is not enough 【 So what we call basic knowledge 【1】 Not yet 】

The length of the longest increasing subsequence has been calculated before —— Here is discontinuous ！！！【 It is a difficult problem for thieves 】
【1】LeetCode High frequency questions 300. The longest increasing subsequence

1 2 perhaps 0 3 Constitute the longest Successive Increasing subsequence , Composed of 2 length
so , How many times does the original array need to be moved ？4-2=2 Time

you 're right , That's it

What principle is this ？？？

You finally want to arr Become non decreasing ,

After sorting the original array , The longest continuously increasing pile with fixed position , It's where we don't need to move , Think about it
19 7 8 25
After ordering , yes 7 8 19 25
78 19 It's moving , But because 19 Move to the right , then 25 Moving to the right automatically OK 了 , that 7 8 Is the number we don't need to move
Therefore, to move is to move 4-2 The length of

this , It's hard to think of

OK, The method is hard to think of , Wei Lai's written examination questions , The scene 3 All the questions are difficult , So no one did it
I can only think offline , Yes, maybe next time ……

We thank the code ！

Give you an array arr, How to find the length of the longest continuous increasing subsequence ？

1 2 0 3
The longest continuous increment , Since it is continuous

Then consider i At the end of the subarray , What is its longest continuous growth ？
It's actually filling in a form dp[i] Said to i At the end of the subarray , What is the length ？

about dp[i], As long as it is [i]>[i-1],dp[i]=do[i-1]+1, Otherwise, it would be 1

Update the maximum value to max that will do

Code of hand tear ：

    // It's actually filling in a form dp[i] Said to i At the end of the subarray , What is the length ？
    public static int longestConsecutiveArrLen(int[] arr){
    
        if (arr == null || arr.length == 0) return 0;
        if (arr.length == 1) return 1;

        int N = arr.length;
        int max = 1;// At least 1
        int[] dp = new int[N];//dp[i] Said to i At the end of the subarray , What is the length 
        // First of all 1
        for (int i = 0; i < N; i++) {
    
            dp[i] = 1;// The most important thing is yourself 
        }
        for (int i = 1; i < N; i++) {
    
            // from 1 Look at the position , As long as it is strictly larger than the front position , Even if the OK
            dp[i] = arr[i] > arr[i - 1] ? dp[i -1] + 1 : 0;
            max = Math.max(max, dp[i]);
        }

        return max;
    }

    public static void test(){
    
        int[] arr = {
    1,2,0,3};
        System.out.println(longestConsecutiveArrLen(arr));
    }

    public static void main(String[] args) {
    
        test();
    }

test ：2
No big problem , As long as it's continuous, it's easy to say

Then let's solve the original problem ！

Input ：
Enter a positive number in the first line n, Representative array arr Number of elements of
The second line , give n A positive integer ai, Represents the elements in an array

Output ：
a number ans, Represents the minimum number of times required to operate the array into a non descending state

The original array arr, The order is arr2
You also need to use arrays map After sorting records arr2 Corresponding to the original array arr The subscript position of

We also need to know the subscript after sorting , You need to package a node , Read in arri And subscripts i Put a node
Also prepare the comparator , use arri Of val Sort , Ascending

        // Add subscript 
        public static class Node{
    
            public int val;
            public int index;// Subscript 

            public Node(int v, int i){
    
                val = v;
                index = i;
            }
        }

        // The comparator 
        public static class cptr implements Comparator<Node> {
    
            @Override
            public int compare(Node o1, Node o2){
    
                return o1.val - o2.val;// Ascending 
            }
        }

okay, Officially tear the code of this problem by hand ：

public static void main(String[] args) {
    
            Scanner in = new Scanner(System.in);
            //  Be careful  hasNext  and  hasNextLine  The difference between 
            int N = in.nextInt();
            Node[] arr = new Node[N];
            for (int i = 0; i < N; i++) {
    
                int val = in.nextInt();
                arr[i] = new Node(val, i);// Pack and put arr
            }
            Arrays.sort(arr, new cptr());// Sort 
            // Install subscripts on the whole node 
            int[] ids = new int[N];
            for (int i = 0; i < N; i++) {
    
                ids[i] = arr[i].index;// Get the position , Then check the length of the longest increasing subarray 
            }
            int max = longestConsecutiveArrLen(ids);
            int ans = N - max;

            System.out.println(ans);
        }

Unable to read arri, hold arri and i The packing is node
Then sort node
Then put the subscript ids Read it out
Use the solution function of the longest strictly increasing subsequence prepared above , hold ids The longest incremental degree of
then N-max That's the result

test ：

6
6 5 4 3 2 1
5

4
19 7 8 25
2

No big problem

The overall time complexity is sorted o(nlog(n))

---

summary

Tips ： Important experience ：

1） The difficulty of this problem lies in how to solve it , You have to make it non decreasing , The longest increment sub array whose position has changed after the original array is sorted , There is no need to move , Its length is the length of immobility
2）N- The length of the longest strictly increasing subsequence is the other position we want to move , Hard to think of, but I've seen , I will understand next time
3） in addition , We don't ask this question , How to find the length of the longest increasing subsequence alone , That question is very classic , It's also very difficult , Want to learn
3） Written examination AC, Space complexity can be ignored , But the interview should consider the optimal time complexity , Also consider the optimal spatial complexity .