单调序列校验的C语言代码问题排查求助

I'm working on a programming problem where I need to check if an input sequence is monotonic (either non-increasing or non-decreasing). The requirement is to output "YES" if it is monotonic, otherwise "NO".

My code works for the test case [1, 2, 3, 3, 2, 1] (outputs "NO" correctly), but fails for [1, 2, 3] and [10, 6, 4, 2, 1, -100] (both should output "YES" but my code isn't handling them right). Here's my code:

#include <stdio.h>
int main() {
    //Inputting the sequence
    int n;
    scanf("%d", &n);
    int a[n];
    for (int i = 1; i <= n; i++) {
        scanf("%d ", &a[i]);
    }
    //Checking monotonic sequence
    for (int i = 1; i <= n; i++) {
        if ((a[i] > a[i-1]) && (a[i] > a[i+1])) {
            printf("NO");
            return;
        } else if ((a[i] < a[i-1]) && (a[i] < a[i+1])) {
            printf("NO");
            return;
        }
    }
    printf("YES");
    return 0;
}

Key Issues in Your Code #

Let's break down why your test cases are failing:

• Array Index Out-of-Bounds
  In C, arrays are 0-indexed. When you declare int a[n], valid indices range from 0 to n-1. Your loop runs from i=1 to i=n:

  • When i = n, accessing a[i] is already out of bounds (the last valid index is n-1).
  • Accessing a[i+1] when i = n-1 will also go out of bounds, leading to undefined behavior that breaks your checks.

• Incorrect Monotonicity Logic
  Your code only checks for "peaks" (elements larger than both neighbors) or "valleys" (elements smaller than both neighbors). This works for sequences with a clear peak/valley like [1,2,3,3,2,1], but it completely misses strictly increasing/decreasing sequences where there are no peaks or valleys. A valid monotonic sequence only needs to follow one consistent trend (non-decreasing OR non-increasing) throughout.

• Input Reading Bug
  The trailing space in scanf("%d ", &a[i]) tells scanf to consume all whitespace after reading the integer. This can cause the program to hang waiting for extra input after the last element is entered, leading to incorrect data being read into the array.

Fixed Code #

Here's a corrected version that addresses all these issues:

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    
    // Edge case: single-element sequence is always monotonic
    if (n <= 1) {
        printf("YES");
        return 0;
    }
    
    int a[n];
    // Use 0-indexing for proper array access
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    
    // Track both possible monotonic trends
    int is_non_decreasing = 1;
    int is_non_increasing = 1;
    
    for (int i = 1; i < n; i++) {
        if (a[i] < a[i-1]) {
            is_non_decreasing = 0;
        }
        if (a[i] > a[i-1]) {
            is_non_increasing = 0;
        }
        // Early exit if neither trend is possible
        if (!is_non_decreasing && !is_non_increasing) {
            printf("NO");
            return 0;
        }
    }
    
    // If either trend holds, the sequence is monotonic
    printf("YES");
    return 0;
}

Explanation of the Fixed Code #

• 0-indexed Array: Uses standard C array indexing to avoid out-of-bounds access errors.
• Trend Tracking: Maintains two flags to check if the sequence follows either a non-decreasing or non-increasing trend.
• Early Termination: Exits immediately if both flags are false, saving unnecessary computation.
• Edge Case Handling: Directly outputs "YES" for single-element sequences, which are trivially monotonic.
• Fixed Input: Removes the trailing space in scanf to ensure correct input reading.

This code will correctly handle all your test cases:

• [1,2,3] → is_non_decreasing remains true → outputs "YES"
• [10,6,4,2,1,-100] → is_non_increasing remains true → outputs "YES"
• [1,2,3,3,2,1] → both flags become false → outputs "NO"

内容的提问来源于stack exchange，提问作者Garrick Jay