[LeetCode]581. Shortest Unsorted Continuous Subarray

题目描述

思路

找出对应的最大最小值，看是否在对应的位置，如果在就向中间缩小，如果都不在，计算长度
暴力解法，平方复杂度
缩小是n，找最大最小是n
优化1，先排序，比较对应位置，时间复杂度 nlogn
继续优化，找局部最大最小可以用动归思路实现，找到好保存状态数组
可以将找最大最小优化到常数时间，最后时间复杂度为n

代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    /* 
    //暴力解法
    int findUnsortedSubarray(vector<int>& nums) {
        int start = 0, end = nums.size() - 1;
        while (start < end) {
            vector<int> minMax = getMinMaxIndex(nums, start, end);
            int min = minMax[0], max = minMax[1];
            if (min != start && max != end)
                break;
            if (min == start)
                start++;
            if (max == end)
                end--;
        }
        return start >= end ? 0 : end - start + 1;
    }

    vector<int> getMinMaxIndex(vector<int> nums, int start, int end) {
        int min = start, max = start;
        for (int i = start; i <= end; ++i) {
            min = nums[i] < nums[min] ? i : min;
            max = nums[i] >= nums[max] ? i : max;
        }
        vector<int> res = { min, max };
        return res;
    }
    */

    /* 
    //排序后的解法
    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> sortArr = nums;
        sort(sortArr.begin(), sortArr.end());
        int start, end;
        for (start = 0; start < nums.size(); ++start) {
            if (nums[start] != sortArr[start])
                break;
        }
        for (end = nums.size() - 1; end >= 0; --end) {
            if (nums[end] != sortArr[end])
                break;
        }
        return start >= end ? 0 : end - start + 1;
    }
    */

    //最后优化
    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> r2lMin = nums, l2rMax = nums;
        r2lMin[nums.size() - 1] = nums[nums.size() - 1], l2rMax[0] = nums[0];
        for (int i = nums.size() - 2; i >= 0; --i) {
            r2lMin[i] = min(nums[i], r2lMin[i + 1]);
        }
        for (int i = 1; i < nums.size(); ++i) {
            l2rMax[i] = max(nums[i], l2rMax[i - 1]);
        }

        int start, end;
        for (start = 0; start < nums.size(); ++start) {
            if (nums[start] != r2lMin[start])
                break;
        }
        for (end = nums.size() - 1; end >= 0; --end) {
            if (nums[end] != l2rMax[end])
                break;
        }
        return start >= end ? 0 : end - start + 1;
    }

};

int main() {
    vector<int> nums = { 1,3,2,3,3 };
    Solution s;
    cout << s.findUnsortedSubarray(nums) << endl;

    system("pause");
    return 0;
}