228. Summary Ranges

O(n) time O(n) space
这道题纯考实现
因为字符串形式的数不方便pop_back所以最好用int来表示数，确认没问题了再把数转成字符串

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<pair<int, int>> v;
        for (int x : nums) {
            if (v.empty() || v.back().second + 1 < x) {
                v.emplace_back(x, x);
            } else {
                v.back().second = x;
            }
        }
        vector<string> res;
        for (const auto &[b, e] : v) {
            if (b == e) {
                res.push_back(to_string(b));
            } else {
                res.push_back(to_string(b) + "->" + to_string(e));
            }
        }
        return res;
    }
};

O(n) time O(1) space
[res.back(), prev, x]

1. res.back() < prev ===> “res.back() -> prev”
2. res.back() == prev ===> “res.back()”即一个孤立的数

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> res;
        int n = nums.size();
        long prev = LONG_MIN; // 初始化prev表示前一个数
        for (int i = 0; i <= n; ++i) { // 因为需要处理最后一个数，所以延长到n
            long x = i == n ? LONG_MAX : nums[i]; // 取当前数
            if (prev + 1 < x) { // 如果不是连续的数
                if (!res.empty() && stoi(res.back()) < prev) { // append
                    res.back() += "->" + to_string(prev);
                }
                if (i < n) { // 把当前新起头的数存起来
                    res.push_back(to_string(x));
                }
            }
            prev = x;
        }
        return res;
    }
};