給定一個數值陣列,判斷其元素是否按「遞增」或「遞減」順序排列。要求時間複雜度 O(n),空間複雜度 O(1),單次遍歷完成判斷。
<?php
/**
* 判斷陣列是否有序(單調遞增或遞減)
* @param array $arr 數值陣列
* @return bool true=有序, false=無序
*/
function isSorted(array $arr): bool {
$len = count($arr);
if ($len < 2) return true; // 0或1個元素視為有序
$trend = 0; // 0=未定, 1=遞增, -1=遞減
for ($i = 1; $i < $len; $i++) {
$diff = $arr[$i] - $arr[$i - 1];
if ($trend === 0) {
// 尚未確定趨勢
if ($diff > 0) $trend = 1;
elseif ($diff < 0) $trend = -1;
// $diff === 0 繼續循環尋找趨勢
} else {
// 已確定趨勢,檢查是否違反
if ($trend === 1 && $diff < 0) return false; // 應遞增卻變小
if ($trend === -1 && $diff > 0) return false; // 應遞減卻變大
}
}
return true; // 遍歷完畢無衝突
}
// 測試用例
$tests = [
[1, 2, 3, 4, 5] => true, // 遞增
[5, 4, 3, 2, 1] => true, // 遞減
[1, 1, 1, 1] => true, // 全等視為有序
[1, 2, 2, 3, 4] => true, // 非嚴格遞增
[1, 3, 2, 4, 5] => false, // 無序
[10, 9, 8, 8, 7] => true, // 非嚴格遞減
[] => true, // 空陣列
[42] => true, // 單元素
];
echo "<pre>";
foreach ($tests as $arr => $expected) {
$result = isSorted($arr);
$status = $result === $expected ? '✅ PASS' : '❌ FAIL';
echo "$status | " . json_encode($arr) . " => " . ($result ? '有序' : '無序') . PHP_EOL;
}
echo "</pre>";
?>
| 方法 | 時間複雜度 | 空間複雜度 | 備註 |
|---|---|---|---|
| 本文單次遍歷法 | O(n) | O(1) | 最優,單趟掃描 |
排序後比較 sort($arr) === $arr | O(n log n) | O(n) | 破壞原陣列,需複製 |
| 兩次遍歷分別檢查升/降序 | O(2n) | O(1) | 常數倍較慢,代碼冗餘 |
單次遍歷配合趨勢旗標是判斷陣列有序性的標準最優解。本文提供的 `isSorted()` 函數代碼簡潔、邏輯清晰、處理了邊界情況,可直接用於生產環境。理解此算法思路對解決「檢測數據單調性」、「流式數據異常檢測」等問題同樣適用。