题解 | 非递减序列

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    bool checkSequence(vector<int>& nums) {
        int n = nums.size();
        int count = 0;  // 记录递减点的个数
        
        // 复制原始序列，用于尝试修改
        vector<int> temp = nums;
        
        for (int i = 0; i < n - 1; i++) {
            if (temp[i] > temp[i + 1]) {
                count++;
                if (count > 1) {
                    return false;
                }
                
                // 尝试修改temp[i]或temp[i+1]
                if (i == 0 || temp[i - 1] <= temp[i + 1]) {
                    temp[i] = temp[i + 1];  // 将temp[i]改小
                } else {
                    temp[i + 1] = temp[i];  // 将temp[i+1]改大
                }
            }
        }
        
        return true;
    }
};

int main() {
    // 读取输入
    vector<int> nums;
    int num;
    while (cin >> num) {
        nums.push_back(num);
    }
    
    // 解决问题
    Solution solution;
    cout << (solution.checkSequence(nums) ? 1 : 0) << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        public boolean checkSequence(int[] nums) {
            int n = nums.length;
            int count = 0;  // 记录递减点的个数
            
            // 复制原始序列，用于尝试修改
            int[] temp = nums.clone();
            
            for (int i = 0; i < n - 1; i++) {
                if (temp[i] > temp[i + 1]) {
                    count++;
                    if (count > 1) {
                        return false;
                    }
                    
                    // 尝试修改temp[i]或temp[i+1]
                    if (i == 0 || temp[i - 1] <= temp[i + 1]) {
                        temp[i] = temp[i + 1];  // 将temp[i]改小
                    } else {
                        temp[i + 1] = temp[i];  // 将temp[i+1]改大
                    }
                }
            }
            
            return true;
        }
    }
    
    public static void main(String[] args) {
        // 读取输入
        Scanner scanner = new Scanner(System.in);
        List<Integer> list = new ArrayList<>();
        while (scanner.hasNextInt()) {
            list.add(scanner.nextInt());
        }
        
        // 转换为数组
        int[] nums = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            nums[i] = list.get(i);
        }
        
        // 解决问题
        Solution solution = new Solution();
        System.out.println(solution.checkSequence(nums) ? 1 : 0);
    }
}

def check_sequence(nums: list) -> bool:
    """检查序列是否可以通过修改一个数变成非递减序列"""
    n = len(nums)
    count = 0  # 记录递减点的个数
    
    # 复制原始序列，用于尝试修改
    nums = nums.copy()
    
    for i in range(n-1):
        if nums[i] > nums[i+1]:
            count += 1
            if count > 1:
                return False
            
            # 尝试修改nums[i]或nums[i+1]
            # 1. 如果是第一个元素，或者nums[i-1]小于等于nums[i+1]
            if i == 0 or nums[i-1] <= nums[i+1]:
                nums[i] = nums[i+1]  # 将nums[i]改小
            else:
                nums[i+1] = nums[i]  # 将nums[i+1]改大
    
    return True

def solve(nums: list) -> int:
    """解决问题的主函数"""
    return 1 if check_sequence(nums) else 0

if __name__ == "__main__":
    # 读取输入
    nums = list(map(int, input().split()))
    
    # 输出结果
    print(solve(nums))