题解 | 队列最小修改

解题思路

这是一个序列操作问题。通过观察可以发现，从后向前看，如果序列是递增的，那么这部分不需要操作。

关键点：

从后向前看，递增序列不需要操作
遇到第一个递减位置时停止
前面的元素都需要移动到队首

算法步骤：

从后向前遍历序列
统计末尾的递增序列长度
剩余的元素数量就是最少操作次数

代码

cpp
java
python

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minMoves(vector<int>& nums) {
        int n = nums.size();
        int result = n - 1;
        
        for (int i = n - 1; i > 0; i--) {
            if (nums[i] > nums[i-1]) {
                result--;
            } else {
                break;
            }
        }
        
        return result;
    }
};

int main() {
    int n;
    cin >> n;
    
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    
    Solution solution;
    cout << solution.minMoves(nums) << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        public int minMoves(int[] nums) {
            int n = nums.length;
            int result = n - 1;
            
            for (int i = n - 1; i > 0; i--) {
                if (nums[i] > nums[i-1]) {
                    result--;
                } else {
                    break;
                }
            }
            
            return result;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        
        Solution solution = new Solution();
        System.out.println(solution.minMoves(nums));
        
        sc.close();
    }
}

def min_moves(nums):
    n = len(nums)
    result = n - 1
    
    for i in range(n - 1, 0, -1):
        if nums[i] > nums[i-1]:
            result -= 1
        else:
            break
            
    return result

# Read input
n = int(input())
nums = list(map(int, input().split()))

print(min_moves(nums))

算法及复杂度

算法：贪心
时间复杂度： $\mathcal{O(n)}$ ，只需要遍历一次数组
空间复杂度： $\mathcal{O(1)}$ ，只使用常数额外空间