1752. Check if Array Is Sorted and Rotated

題目 / Problem

中文 給定一個整數陣列 nums，判斷它是否原本是「非遞減排序」的陣列，再經過任意次數（包含 0 次）的旋轉而得。原陣列允許有重複元素。若是，回傳 true；否則回傳 false。

旋轉的定義：陣列 A 旋轉 x 個位置會得到陣列 B，使得對所有合法索引 i，B[i] == A[(i+x) % A.length]。

English Given an integer array nums, return true if it could have been obtained by sorting some array in non-decreasing order and then rotating it some number of positions (including 0). Duplicates are allowed in the original array.

A rotation of A by x positions produces B such that B[i] == A[(i+x) % A.length] for every valid i.

Constraints - 1 <= nums.length <= 100 - 1 <= nums[i] <= 100

Example - Input: nums = [3,4,5,1,2] - Output: true - 解釋 / Explanation：原本的排序陣列是 [1,2,3,4,5]，向右旋轉 3 個位置（或等價地，從索引 2 開始繞一圈）即可得到 [3,4,5,1,2]。

名詞解釋 / Glossary

• 非遞減排序 / Non-decreasing order：陣列中每個元素都 >= 前一個元素，允許相鄰元素相等（例如 [1,2,2,3]）。和「嚴格遞增」不同。
• 旋轉 / Rotation：把陣列的前 k 個元素整段搬到末端（或反過來），長度不變、元素不變，只是起點被改變。例如 [1,2,3,4,5] 旋轉 2 次後變成 [3,4,5,1,2]。
• 斷點 / Break point：指陣列中 nums[i] > nums[i+1] 的位置，也就是「下降」發生的地方。一個排序且旋轉過的陣列最多只有一個斷點。
• 環狀比較 / Circular comparison：把陣列當成首尾相連的環，用 (i+1) % n 取「下一個」索引，這樣最後一個元素的下一個就是第一個元素。常用於旋轉相關問題。
• 模運算 % / Modulo operator：取餘數。(i+1) % n 可確保索引在 [0, n-1] 範圍內，自然形成環狀結構。

思路

最直觀的暴力做法是：把每一個索引 k 都當作「原排序陣列的起點」，假設這就是旋轉量，然後重新排出 nums[k], nums[k+1], ..., nums[k-1]（環狀），檢查這個序列是否非遞減。一共要試 n 個起點，每次檢查 O(n)，總共 O(n²)。對 n <= 100 雖然能過，但其實有更乾淨的觀察：一個「排序後再旋轉」的陣列，沿著環走一圈，最多只會出現「一個」下降的地方（就是原本排序陣列的尾端接回頭端的那個接縫）。如果根本沒有旋轉，下降次數是 0；如果有旋轉，下降次數恰好是 1；如果是 2 次以上，那它不可能是排序後再旋轉而成的。所以我們只要把陣列當成環，數一下有幾個 i 滿足 nums[i] > nums[(i+1) % n]，這個計數若 <= 1 就回傳 true，否則 false。關鍵在於使用 % n 來處理最後一個元素回到第一個元素的比較，否則會漏掉「接縫」這個重要的位置。

The brute-force idea is to try every index k as the candidate starting point of the original sorted array, rebuild the sequence nums[k], nums[k+1], ..., nums[k-1] cyclically, and check whether it is non-decreasing. That costs O(n²), which fits the tiny constraints but misses a cleaner observation. If you imagine the array laid out on a circle and walk around it once, a "sorted-then-rotated" array can contain at most one descent — namely the seam where the largest element of the original array wraps back to the smallest. Zero rotations means zero descents; any non-zero rotation means exactly one descent; anything with two or more descents cannot be produced by sorting then rotating. So the entire problem collapses to counting, over the cyclic neighbors (i, (i+1) % n), how many pairs satisfy nums[i] > nums[(i+1) % n]. If that count is <= 1, return true; otherwise false. The modulo % n is essential — without it we would miss the wrap-around pair (nums[n-1], nums[0]), which is exactly where the seam lives.

逐步走查 / Walkthrough

以 nums = [3,4,5,1,2]，長度 n = 5 為例。我們維護一個計數器 drops（下降次數），初始為 0，然後對每個 i 從 0 到 n-1，比較 nums[i] 和 nums[(i+1) % n]。

Tracing with nums = [3,4,5,1,2], n = 5. We keep a counter drops starting at 0, then iterate i from 0 to 4, comparing nums[i] with nums[(i+1) % 5].

最終 drops = 1，1 <= 1，所以回傳 true。注意 i = 4 那一步是「環狀」比較：拿最後一個元素 2 和第一個元素 3 比較，這個比較沒有下降，正好對應原排序陣列 [1,2,3,4,5] 中 2 接到 3 的位置。

Final drops = 1, and 1 <= 1, so we return true. The i = 4 step is the wrap-around comparison: last element 2 vs. first element 3. It is not a drop, which lines up perfectly with the original sorted array [1,2,3,4,5] where 2 is followed by 3.

Solution — C

// 演算法：把陣列當成首尾相連的環，數有幾個位置 nums[i] > nums[(i+1) % n]。
// Algorithm: treat the array as a circle and count positions where
// nums[i] > nums[(i+1) % n]. A sorted-then-rotated array has at most one such
// "drop" (the seam). If we see two or more drops, it cannot be sorted+rotated.

#include <stdbool.h>   // 引入 bool / pull in the bool type

// LeetCode 的 C 介面：nums 是輸入陣列指標，numsSize 是長度。
// LeetCode C signature: nums is a pointer to the input array, numsSize its length.
bool check(int* nums, int numsSize) {
    int drops = 0;                              // 計算下降次數 / count of descents
    for (int i = 0; i < numsSize; i++) {        // 走訪每一個索引 i / iterate every index i
        // (i + 1) % numsSize 把 i = numsSize-1 的「下一個」繞回到 0。
        // (i + 1) % numsSize wraps the "next index" of the last position back to 0,
        // giving us the circular neighbor.
        int next = (i + 1) % numsSize;          // 下一個索引（環狀）/ next index (circular)
        if (nums[i] > nums[next]) {             // 出現下降 / a descent occurred
            drops++;                            // 累加下降次數 / increment the counter
            if (drops > 1) return false;        // 超過 1 次直接失敗，提早結束 / >1 → fail fast
        }
    }
    // drops 為 0（完全沒旋轉）或 1（有一個接縫）都合法。
    // drops == 0 (no rotation) or drops == 1 (one seam) are both valid.
    return true;
}

Solution — C++

// 演算法：與 C 版本相同 — 把陣列視為環狀，數有幾個 nums[i] > nums[(i+1) % n] 的位置。
// 若 <= 1 個下降，就是「排序後旋轉」而成；否則不是。
// Algorithm: same as the C version — treat the array as circular, count positions
// where nums[i] > nums[(i+1) % n]; <= 1 such drop means sorted-then-rotated.

#include <vector>      // 引入 std::vector / pull in std::vector

class Solution {
public:
    // LeetCode C++ 介面：傳入一個 vector<int>，回傳 bool。
    // 用 const 參考避免複製整個 vector / use const-reference to avoid copying the vector.
    bool check(const std::vector<int>& nums) {
        int n = static_cast<int>(nums.size()); // 取得長度，轉成 int 避免 size_t 比較警告
                                               // get length, cast to int to avoid signed/unsigned warnings
        int drops = 0;                         // 下降次數計數器 / counter for descents
        for (int i = 0; i < n; ++i) {          // 範圍式 for 也可以，這裡用索引以便取 (i+1)%n
                                               // could use range-for, but we need the index for (i+1)%n
            int next = (i + 1) % n;            // 環狀的下一個索引 / circular next index
            if (nums[i] > nums[next]) {        // 若當前比下一個還大 → 下降 / current > next → drop
                if (++drops > 1) return false; // 先自增再比較；> 1 立刻回傳 false / pre-increment then test
            }
        }
        return true;                           // 0 或 1 個下降皆合法 / 0 or 1 drop is valid
    }
};

複雜度 / Complexity

• Time: O(n) — 我們只對陣列做一次線性掃描，每個元素比較一次（含環狀繞回的那一次），所以時間正比於陣列長度 n。We perform a single linear pass over the array, doing one comparison per element (including the wrap-around), so the running time scales linearly with the array length n.
• Space: O(1) — 只用了 drops、i、next 等少量整數變數，沒有開額外的陣列或雜湊表，所以額外空間是常數。We only use a few integer variables (drops, i, next); no auxiliary arrays or hash tables are allocated, so the extra space is constant.

Pitfalls & Edge Cases

• 忘記環狀比較 / Forgetting the wrap-around：如果只比較 i 到 n-2，會漏掉 nums[n-1] 和 nums[0] 的關係，導致像 [2,1] 這種無效輸入被誤判為 true。我們用 (i+1) % n 並讓 i 跑到 n-1，自然處理接縫。Comparing only up to i < n-1 misses the nums[n-1] vs. nums[0] pair and would wrongly accept inputs like [2,1]. Using (i+1) % n with i running to n-1 handles the seam naturally.
• 重複元素 / Duplicates：原題說「非遞減」，所以 nums[i] == nums[i+1] 不算下降。我們的條件用嚴格 >，正好正確處理 [1,1,1]、[2,2,2,1,2] 等情況。The problem says "non-decreasing", so nums[i] == nums[i+1] is not a drop. Our strict > comparison correctly accepts cases like [1,1,1] and [2,2,2,1,2].
• 長度為 1 的陣列 / Single-element array：當 n = 1，迴圈只跑一次，比較 nums[0] 和 nums[0]，永遠不會下降，回傳 true，正確。When n = 1, the loop compares nums[0] with itself, never registers a drop, and returns true — the correct answer.
• 完全沒旋轉的情況 / Zero rotations：[1,2,3] 的下降次數是 0，仍然符合 drops <= 1，所以會正確回傳 true。An unrotated sorted array has 0 drops, which still satisfies drops <= 1, so it is correctly accepted.
• 提早結束最佳化 / Early-exit optimization：一旦 drops > 1 就立刻 return false，避免無謂的繼續掃描；雖然在 n <= 100 規模下效果不明顯，但養成這個習慣對更大規模的問題有幫助。Returning false as soon as drops > 1 avoids needless work; the savings are negligible at n <= 100 but it's a good habit for larger problems.