C++数组极值点查找算法补充实现及“无极端点等价于数组有序”的验证问询

Hey there! Let's work through your two tasks one by one.

1. Modifying the Code to Output "SORTED" When No Extreme Points Exist #

Your current code correctly identifies and prints extreme points, but it doesn't handle the case where there are none. The fix is straightforward: we'll add a counter to track how many extreme points we find. After checking all possible indices, if the counter stays at 0, we print "SORTED"; otherwise, we'll have already printed the found points.

Here's the revised complete code with comments explaining key changes:

#include <iostream>
using namespace std;

bool isExtremePoint(int num, int leftNeighbour, int rightNeighbour);

int main() {
    int array[] = { 0, 5, 3, 6, 8, 7, 15, 9 };
    int size = sizeof(array) / sizeof(array[0]);
    int extremeCount = 0;

    for (int i = 1; i < size - 1; i++) {
        if (isExtremePoint(array[i], array[i - 1], array[i + 1])) {
            cout << array[i] << " ";
            extremeCount++;
        }
    }

    // Handle the no-extreme-points case
    if (extremeCount == 0) {
        cout << "SORTED";
    }

    cout << endl;
    return 0;
}

// Simplified function - removed unused parameters for clarity
bool isExtremePoint(int num, int leftNeighbour, int rightNeighbour) {
    // Check for peak OR valley condition
    return (num > leftNeighbour && num > rightNeighbour) || 
           (num < leftNeighbour && num < rightNeighbour);
}

Key Updates: #

• Added extremeCount to keep track of how many extreme points are found.
• Added a post-loop check: if extremeCount is 0, print "SORTED".
• Cleaned up the isExtremePoint function by removing unused arr and size parameters.

2. Verifying the Claim: "An array has no extreme points if and only if it is sorted" #

This claim is false. Let's break down both directions of the statement:

First Direction (True): A sorted array has no extreme points #

For a strictly ascending sorted array, every middle element A[i] follows A[i-1] < A[i] < A[i+1] — it's neither a peak nor a valley. For a strictly descending sorted array, A[i-1] > A[i] > A[i+1] — same logic, no extreme points. Even non-strict sorted arrays (like [1,2,2,3]) avoid extreme points, since no middle element meets the strict greater/less conditions required for peaks or valleys.

Reverse Direction (False): No extreme points does NOT mean the array is sorted #

There are non-sorted arrays that have no extreme points. Examples include:

• [1,3,3,2]: The middle elements are 3 and 3. Index 1: 1 < 3 == 3 (not a peak, since it's not strictly greater than the right neighbor). Index 2: 3 == 3 > 2 (not a valley, since it's not strictly less than the left neighbor). No extreme points here, but the array isn't sorted.
• [5,5,5]: All elements are equal. No middle element satisfies the peak/valley rules, and this array isn't "sorted" in the traditional strictly increasing/decreasing sense.
• [2,2,4,4,1,1]: This array has plateaus and a drop, but no middle element qualifies as a peak or valley (adjacent elements are equal in plateaus, and transitions don't meet strict comparison rules).

Final Conclusion #

The "if and only if" statement fails because non-sorted arrays with consecutive equal elements can avoid creating extreme points, even though they aren't strictly monotonic.

内容的提问来源于stack exchange，提问作者Willow Hill